#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,h,k,a[100001];
pair <int, int> p[100001];
long long sum,res;
set <int> s;
void update(int i, int j){
a[i]+=j;
if (a[i])
s.insert(i);
else
s.erase(i);
}
int32_t main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n;
for (int i=1;i<=n;i++)
cin >> p[i].first >> p[i].second;
sort(p+1,p+n+1);
s.insert(1);
s.insert(n+1);
for (int i=1;i<=n;i++){
auto [h,k]=p[i];
if (a[h-k+1]){
update(h-k+1,1);
update(h+1,-1);
continue;
}
auto it=s.lower_bound(h-k+1);
int r=*it;
it--;
int l=*it;
r--;
r=min(r,h);
update(l,1);
update(l+r-h+k,-1);
update(r+1,1);
update(h+1,-1);
}
for (int i=1;i<=n;i++){
sum+=a[i];
res+=sum*(sum-1)/2;
}
cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
3928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
3012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
3152 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
36 ms |
4944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
3392 KB |
Output is correct |
2 |
Correct |
20 ms |
3728 KB |
Output is correct |