#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 7
#define MAXN 100005
vector<pair<int,int>> masts;
int sg[4*MAXN], lazy[4*MAXN];
void increment(int k, int a, int b, int q_l, int q_r) {
if (lazy[k]) {
sg[k] += (b-a+1) * lazy[k];
if (a != b) {
lazy[2*k] += lazy[k];
lazy[2*k+1] += lazy[k];
}
lazy[k] = 0;
}
if (q_r < a || q_l > b)
return ;
if (q_l <= a && b <= q_r) {
sg[k] += b-a+1;
if (a != b) {
lazy[2*k]++;
lazy[2*k+1]++;
}
return ;
}
increment(2*k, a, (a+b)/2, q_l, q_r);
increment(2*k+1, (a+b)/2+1, b, q_l, q_r);
sg[k] = sg[2*k] + sg[2*k+1];
}
ll query(int k, int a, int b, int plc) {
if (lazy[k]) {
sg[k] += (b-a+1) * lazy[k];
if (a != b) {
lazy[2*k] += lazy[k];
lazy[2*k+1] += lazy[k];
}
lazy[k] = 0;
}
if (b < plc || a > plc)
return 0;
if (a == b)
return sg[k];
return query(2*k, a, (a+b)/2, plc) + query(2*k+1, (a+b)/2+1, b, plc);
}
int main() {
fast
int N, H, K;
cin >> N;
masts = vector<pair<int,int>>(N);
for (int i = 0; i < N; i++) {
cin >> H >> K;
masts[i] = {H, K};
}
sort(masts.begin(), masts.end());
int left = 100001 - masts[0].f;
for (int i = 0; i < N; i++) {
left = 100001 - masts[i].f;
int q = query(1, 1, 100000, 100000);
int R = 100000, L = left;
int ans = -1;
while (R >= L) {
int mid = L + (R-L)/2;
if (query(1, 1, 100000, mid) != q) {
ans = mid;
L = mid + 1;
} else
R = mid - 1;
}
if (ans == -1) {
increment(1, 1, 100000, 100001-masts[i].s, 100000);
} else {
increment(1, 1, 100000, max(left, ans - masts[i].s + 1), ans);
if (ans - masts[i].s + 1 < left) {
increment(1, 1, 100000, 100000 - masts[i].s + ans - left + 2, 100000);
}
}
}
ll ans = 0;
for (int i = 1; i <= 100000; i++) {
ll q = query(1, 1, 100000, i);
ans += q * (q-1) / 2;
}
cout << ans << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
340 KB |
Output is correct |
2 |
Correct |
14 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
368 KB |
Output is correct |
2 |
Incorrect |
12 ms |
380 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
32 ms |
1112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
80 ms |
1488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
149 ms |
2320 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
277 ms |
3796 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
288 ms |
4060 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
351 ms |
4312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |