#include <bits/stdc++.h>
using namespace std;
struct stree
{
vector<int>tree;
int N;
stree(int n){
N=1;
while(N<n)
N*=2;
tree.resize(N*3);
N--;
}
int query(int x)
{
return tree[x+N+N+1];
}
void add(int x, int val)
{
x+=N+N+1;
tree[x]+=val;
if(tree[x]!=0)
tree[x-N-1]=1;
else
tree[x-N-1]=0;
x-=N;
x--;
x/=2;
while(x)
{
tree[x]=tree[x*2]+tree[x*2+1];
x/=2;
}
}
int first_right(int v, int tl, int tr, int l, int r)
{
if(l>r||tree[v]==0)
return -1;
if(tl==tr)
return tl;
int tm=(tl+tr)/2;
int res=-1;
if(l<=tm)
res=first_right(v*2,tl,tm,l,min(r,tm));
if(res==-1&&r>tm)
res=first_right(v*2+1,tm+1,tr,max(l,tm+1),r);
return res;
}
int first_right(int x)
{
return first_right(1,1,N+1,x,N+1);
}
int first_left(int v, int tl, int tr, int l, int r)
{
if(l>r||tree[v]==0)
return -1;
if(tl==tr)
return tl;
int tm=(tl+tr)/2;
int res=-1;
if(r>tm)
res=first_left(v*2+1,tm+1,tr,max(l,tm+1),r);
if(res==-1&&l<=tm)
res=first_left(v*2,tl,tm,l,min(r,tm));
return res;
}
int first_left(int x)
{
return first_left(1,1,N+1,1,x);
}
};
int main()
{
int n;
cin>>n;
vector<pair<int,int>>hk(n);
for(int i=0; i<n; i++)
cin>>hk[i].first>>hk[i].second;
sort(hk.begin(),hk.end());
stree tr(hk[hk.size()-1].first+1);
int h,k;
for(int i=0; i<n; i++)
{
h=hk[i].first;
k=hk[i].second;
int a,b;
if(tr.query(h-k+1)!=0)
a=h-k+1;
else
{
a=tr.first_right(h-k+1);
int hml=k-(h+1-a);
if(a==-1)
a=h+1,hml=k;
b=tr.first_left(h-k+1);
if(b==-1)
b=1;
tr.add(b,1);
tr.add(b+hml,-1);
}
tr.add(a,1);
tr.add(h+1,-1);
}
int sm=0;
long long int res;
for(int i=1; i<=h; i++)
{
sm+=tr.query(i);
res+=(sm*(sm-1)/2);
}
cout<<res<<"\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... |