#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
pair<int, int> stick[100005]; int maxh;
int st[400005]; int lz[400005];
void push(int p, int cl, int cr) {
if (cl >= cr) return;
st[p*2] += lz[p];
st[p*2+1] += lz[p];
lz[p*2] += lz[p];
lz[p*2+1] += lz[p];
lz[p] = 0;
}
void update(int ql, int qr, int v, int p=1, int cl=1, int cr=maxh) {
if (ql <= cl && qr >= cr) {
st[p]+=v; lz[p] += v; return;
}
push(p, cl, cr);
int mid = (cl+cr)/2;
if (ql <= mid) update(ql, qr, v, p*2, cl, mid);
if (qr > mid) update(ql, qr, v, p*2+1, mid+1, cr);
st[p] = min(st[p*2], st[p*2+1]);
}
int pquery(int x, int p=1, int cl=1, int cr=maxh) {
if (cl == cr) return st[p];
push(p, cl, cr);
int mid = (cl+cr)/2;
if (x <= mid) return pquery(x, p*2, cl, mid);
else return pquery(x, p*2+1, mid+1, cr);
}
int walk(int x, int p=1, int cl=1, int cr=maxh) {
// find first smaller than x
if (cl == cr) return cl;
push(p, cl, cr);
int mid = (cl+cr)/2;
if (st[p*2]<x) return walk(x, p*2, cl, mid);
else return walk(x, p*2+1, mid+1, cr);
}
signed main() {
int n; cin>>n;
for (int i = 1; i <= n; i++) {
cin>>stick[i].first>>stick[i].second;
maxh = max(maxh, stick[i].first);
}
sort(stick+1, stick+n+1);
for (int i = 1; i <= n; i++) {
//cout<<stick[i].second<<endl;
int hval = pquery(stick[i].first-stick[i].second+1);
int finst = walk(hval+1);
int nextdown = walk(hval);
int aff = min(stick[i].first, nextdown-1)-(stick[i].first-stick[i].second+1);
//cout<<"update " <<finst<<" "<<finst+aff<<endl;
//cout<<"update "<<nextdown<<" "<<stick[i].first<<endl;
update(finst, finst+aff, 1);
update(nextdown, stick[i].first, 1);
// for (int i = 1; i <= n; i++) {
// cout<<pquery(i)<<" ";
// }
// cout<<endl;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int x = pquery(i);
//cout<<x<<endl;
ans += 0.5*(x-1)*x;
}
cout<<ans;
}
# | 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... |