제출 #1024167

#제출 시각아이디문제언어결과실행 시간메모리
1024167lucriSails (IOI07_sails)C++17
90 / 100
1026 ms10852 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...