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;
long long n;
long long ans;
pair<long long,long long>v[100010],tr;
struct intervale{long long vmin,vmax,lazy;}aint[400010];
void qsort(long long b,long long e)
{
if(b>=e)
return;
long long bb=b,ee=e,adb=1,ade=0;
while(bb<ee)
{
if(v[bb].first>v[ee].first)
{
tr=v[bb];
v[bb]=v[ee];
v[ee]=tr;
adb=1-adb;
ade=1-ade;
}
bb+=adb;
ee-=ade;
}
qsort(b,bb-1);
qsort(bb+1,e);
}
void propaga(long long poz,long long b,long long e)
{
if(b!=e)
{
aint[poz*2].lazy+=aint[poz].lazy;
aint[poz*2+1].lazy+=aint[poz].lazy;
}
aint[poz].vmax+=aint[poz].lazy;
aint[poz].vmin+=aint[poz].lazy;
aint[poz].lazy=0;
}
long long valoare(long long poz,long long b,long long e,long long pozc)
{
propaga(poz,b,e);
if(b==e)
return aint[poz].vmin;
if((b+e)/2>=pozc)
return valoare(poz*2,b,(b+e)/2,pozc);
else
return valoare(poz*2+1,(b+e)/2+1,e,pozc);
}
void adauga(long long poz,long long b,long long e,long long bi,long long ei)
{
if(b>ei||bi>e)
return;
propaga(poz,b,e);
if(bi<=b&&e<=ei)
{
++aint[poz].lazy;
return;
}
adauga(poz*2,b,(b+e)/2,bi,ei);
adauga(poz*2+1,(b+e)/2+1,e,bi,ei);
aint[poz].vmin=aint[poz*2+1].vmin+aint[poz*2+1].lazy;
aint[poz].vmax=aint[poz*2].vmax+aint[poz*2].lazy;
}
long long cauta1(long long poz,long long b,long long e,long long val)
{
propaga(poz,b,e);
if(b==e)
return b;
if(aint[poz*2].vmin+aint[poz*2].lazy<=val)
return cauta1(poz*2,b,(b+e)/2,val);
return cauta1(poz*2+1,(b+e)/2+1,e,val);
}
long long cauta2(long long poz,long long b,long long e,long long val)
{
propaga(poz,b,e);
if(b==e)
return b;
if(aint[poz*2+1].vmax+aint[poz*2+1].lazy>=val)
return cauta2(poz*2+1,(b+e)/2+1,e,val);
return cauta2(poz*2,b,(b+e)/2,val);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
cin>>n;
for(long long i=1;i<=n;++i)
cin>>v[i].first>>v[i].second;
swap(v[1],v[rand()%n+1]);
qsort(1,n);
for(long long i=1;i<=n;++i)
{
long long poz=v[i].first-v[i].second+1;
long long val=valoare(1,1,100001,poz);
long long poz1=cauta1(1,1,100001,val);
long long poz2=min(cauta2(1,1,100001,val),v[i].first);
adauga(1,1,100001,poz1,poz1+(poz2-poz));
adauga(1,1,100001,poz2+1,v[i].first);
}
for(long long i=1;i<=100001;++i)
{
long long val=valoare(1,1,100001,i);
ans+=val*(val-1)/2;
}
cout<<ans;
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... |