#include <bits/stdc++.h>
using namespace std;
#define task ""
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int MAX = 100100;
const int CC = 100000;
int n;
int bit[MAX];
void updateValue(int id, int delta) {
for (; id <= CC; id += id & -id)
bit[id] += delta;
}
void updateValue(int l, int r, int delta) {
if (l > r) return;
updateValue(l, +delta);
updateValue(r + 1, -delta);
}
int getValue(int id) {
int res = 0;
for (; id > 0; id -= id & -id)
res += bit[id];
return res;
}
int getPos(int value) {
int cur = 0, curValue = 0;
for (int j = 16; j >= 0; --j) if (cur + (1 << j) <= CC) {
if (curValue + bit[cur + (1 << j)] <= value) {
cur += 1 << j; curValue += bit[cur];
}
}
return cur;
}
long long bit1[MAX];
long long bit2[MAX];
void updateSum(long long bit[], int id, long long delta) {
for (; id <= CC; id += id & -id)
bit[id] += delta;
}
void updateSum(int l, int r, long long delta) {
if (l > r) return;
updateSum(bit1, l, +delta);
updateSum(bit1, r + 1, -delta);
updateSum(bit2, l, +1LL * l * delta);
updateSum(bit2, r + 1, -1LL * (r + 1) * delta);
}
long long getSum(long long bit[], int id) {
long long res = 0;
for (; id > 0; id -= id & -id)
res += bit[id];
return res;
}
long long getSum(int u) { return 1LL * (u + 1) * getSum(bit1, u) - getSum(bit2, u); }
long long getSum(int u, int v) { return getSum(v) - getSum(u - 1); }
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n;
long long ans = 0;
for (int i = 1; i <= n; ++i) {
int h, k;
cin >> h >> k;
h = CC - h + 1;
ans += getSum(h, h + k - 1);
int lastValue = getValue(h + k - 1);
int lt = getPos(lastValue - 1), rt = getPos(lastValue);
if (lt < h) {
updateSum(rt - k + 1, rt, +1);
updateValue(rt - k + 1, rt, +1);
} else {
updateSum(h, lt, +1); updateValue(h, lt, +1); k -= lt - h + 1;
updateSum(rt - k + 1, rt, +1); updateValue(rt - k + 1, rt, +1);
}
}
cout << ans;
return 0;
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
10 ms |
1232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
1748 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
3128 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
39 ms |
3296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
45 ms |
3396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |