#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int maxn = 1e5 + 20;
pair<int, int> a[maxn];
int cnt[maxn];
void update(int lt, int rt) {
for (int i = lt; i <= rt; i++) {
cnt[i]++;
}
}
void just_do_it() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a + 1, a + n + 1);
int h = a[n].first;
for (int i = 1; i <= n; i++) {
int rt2 = a[i].first;
int rem = a[i].second;
int val = cnt[rt2 - rem + 1];
int rt1 = -1;
for (int j = 1; j <= h; j++) {
if (cnt[j] >= val) {
rt1 = j;
}
else {
break;
}
}
int lt = -1;
for (int j = h; j >= 1; j--) {
if (cnt[j] <= val) {
lt = j;
}
else {
break;
}
}
if (rt1 < rt2) {
update(rt1 + 1, rt2);
rem -= rt2 - rt1;
}
if (rem > 0) {
update(lt, lt + rem - 1);
}
}
long long res = 0;
for (int i = 1; i <= h; i++) {
res += 1LL * cnt[i] * (cnt[i] - 1) / 2;
}
cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
340 KB |
Output is correct |
2 |
Correct |
64 ms |
660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
552 KB |
Output is correct |
2 |
Correct |
97 ms |
556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
594 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1080 ms |
984 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1077 ms |
1252 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1072 ms |
1304 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1069 ms |
1304 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |