This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000;
vector<int> mn(4*(N+5),0);
vector<int> mx(4*(N+5),0);
vector<int> lazy(4*(N+5),0);
void pull(int idx)
{
mn[idx]=min(mn[2*idx],mn[2*idx+1]);
mx[idx]=max(mx[2*idx],mx[2*idx+1]);
}
void apply(int idx,int x)
{
mn[idx]+=x;
mx[idx]+=x;
lazy[idx]+=x;
}
void push(int idx)
{
for(int i=0;i<2;i++) apply(2*idx+i,lazy[idx]);
lazy[idx]=0;
}
void update(int idx,int l,int r,int ql,int qr,int x)
{
if(ql>qr) return;
if(l==ql&&r==qr) apply(idx,x);
else
{
int m=(l+r)/2;
push(idx);
update(2*idx,l,m,ql,min(qr,m),x);
update(2*idx+1,m+1,r,max(ql,m+1),qr,x);
pull(idx);
}
}
int query(int idx,int l,int r,int pos)
{
if(l==r) return mn[idx];
int m=(l+r)/2;
push(idx);
if(pos<=m) return query(2*idx,l,m,pos);
else return query(2*idx+1,m+1,r,pos);
}
int descend(int idx,int l,int r,int ql,int qr,int val,int dir)
{
if(ql>qr) return -1;
if(!(mn[idx]<=val&&val<=mx[idx])) return -1;
if(l==r) return l;
int m=(l+r)/2;
push(idx);
if(dir==0)
{
int t=descend(2*idx,l,m,ql,min(qr,m),val,dir);
if(t!=-1) return t;
return descend(2*idx+1,m+1,r,max(ql,m+1),qr,val,dir);
}
else
{
int t=descend(2*idx+1,m+1,r,max(ql,m+1),qr,val,dir);
if(t!=-1) return t;
return descend(2*idx,l,m,ql,min(qr,m),val,dir);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<array<int,2>> v(n+1,{0,0});
for(int i=1;i<=n;i++)
{
auto &[h,k]=v[i];
cin >> h >> k;
}
sort(v.begin(),v.end());
int p=N+1;
for(int i=1;i<=n;i++)
{
auto [h,k]=v[i];
p-=(h-v[i-1][0]);
int a=query(1,1,N,p+k-1);
int l=descend(1,1,N,p,N,a,0);
int r=descend(1,1,N,p,N,a,1);
int cnt=(p+k-1-l+1);
update(1,1,N,p,l-1,1);
update(1,1,N,r-cnt+1,r,1);
}
ll res=0;
for(int i=1;i<=N;i++)
{
ll c=query(1,1,N,i);
res+=((c-1)*c/2);
}
cout << res << "\n";
return 0;
}
# | 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... |