티스토리 뷰
현재 심는 나무 위치 기준으로 왼쪽, 오른쪽 나눠서 생각한다. 왼쪽에 있는 모든 나무와 현재 새로 심을 나무의 거리 차이의 합은 왼쪽에 있는 나무의 개수 * (현재 위치) - 왼쪽 나무의 거리합이고 오른쪽에 있는 모든 나무와 현재 새로 심을 나무의 거리 차이의 합은 오른쪽에 있는 나무의 거리합 - (현재 위치) * 오른쪽에 있는 나무의 개수이다.
주의점은 같은 곳에 나무를 여러 번 심을 수 있다는 점. 오버플로우를 주의해야 한다는 점. % 연산과 * 연산의 순위가 같기 때문에 괄호 잘 쳐야된다는 점. 첫 번째 나무를 심을 때는 곱을 하면 안 된다는 점 등이 있다. 필자는 첫 번째 나무를 심은 경우를 넘기기 위해 거리합이 0인 경우를 다 넘겼는데, 이것 때문에 2시간 동안 삽질했다. 거리 % MOD가 0인 경우 있는데, 이를 같이 넘겨버린 것. 이걸 생각 못하고 내 논리에 문제가 없는데 왜 틀렸냐며 반례를 찾아다녔다 ㅎㅎ 내 혈압
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll cntT[1 << 21], distT[1 << 21];
ll base, n;
void update(ll k) {
k += base;
cntT[k]++;
distT[k] += (k - base);
for (k /= 2; k > 0; k /= 2) {
cntT[k] = cntT[2 * k] + cntT[2 * k + 1];
distT[k] = distT[2 * k] + distT[2 * k + 1];
}
}
ll dist(ll a, ll b) {
a += base; b += base;
ll res = 0;
while (a <= b) {
if (a % 2 == 1) res += distT[a++];
if (b % 2 == 0) res += distT[b--];
a /= 2; b /= 2;
}
return res;
}
ll cnt(ll a, ll b) {
a += base; b += base;
ll res = 0;
while (a <= b) {
if (a % 2 == 1) res += cntT[a++];
if (b % 2 == 0) res += cntT[b--];
a /= 2; b /= 2;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (base = 1; base < 200001; base *= 2);
ll ans = 1;
for (int i = 0; i < n; i++) {
ll t; cin >> t;
ll cur = (t * cnt(0, t - 1) - dist(0, t - 1)) + (dist(t + 1, 200000) - t * cnt(t + 1, 200000));
update(t);
if (i == 0) continue;
ans = ((ans % MOD) * (cur % MOD)) % MOD;
}
cout << ans;
return 0;
}
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- boj 10473
- Ugly Numbers
- boj 9345
- 백준 16562
- 백준 3006
- 백준 9345
- 제로베이스 스쿨
- boj 16562
- boj 3006
- 백준 2336
- 디지털 비디오 디스크
- boj 14868
- boj 12713
- 백준 2243
- 터보소트
- 백준 1280
- 제로베이스 백엔드 스쿨
- 백준 12713
- boj 2243
- boj 2336
- boj 1280
- 백준 10473
- 백준 10775
- 백준 14868
- 백준 1106
- 사탕상자
- 부트 캠프
- boj 1106
- boj 10775
- 인간 대포
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함