#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
struct fenwick {
int n;
vector<ll> tree;
fenwick(int _n) : n(_n+10), tree(n+20) {}
void update(int p, ll v) {
for(p++; p<n; p+=p&-p) tree[p] += v;
}
ll query(int p) {
ll ans = 0;
for(p++; p; p-=p&-p) ans += tree[p];
return ans;
}
void update(int l, int r, ll v) {
update(l, v);
update(r+1, -v);
}
} fwt(N);
signed main() {
int n; cin >> n;
vector<array<int, 2> > a(n+1);
for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
sort(a.begin()+1, a.end());
ll ans = 0;
fwt.update(0, 0, (ll)1e10);
for(int i=1; i<=n; i++) {
int R = a[i][0], L = a[i][0]-a[i][1]+1;
if(fwt.query(L) < fwt.query(L-1)) {
fwt.update(L, R, 1);
continue;
}
int l=L, r=R, c=1;
while(l <= r) {
int mid = (l + r) / 2;
if(fwt.query(L) == fwt.query(mid)) c = mid-L+1, l = mid + 1;
else r = mid - 1;
}
l=1, r=L;
int p = L;
while(l <= r) {
int mid = (l + r) / 2;
if(fwt.query(mid) == fwt.query(L)) p = mid, r = mid - 1;
else l = mid + 1;
}
fwt.update(p, p+c-1, 1);
if(L+c <= R) fwt.update(L+c, R, 1);
}
for(int i=1; i<N; i++) {
ll x = fwt.query(i);
ans += x * (x - 1) / 2;
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |