Submission #310767

#TimeUsernameProblemLanguageResultExecution timeMemory
310767mosiashvililukaInterval Collection (CCO20_day2problem2)C++17
0 / 25
2137 ms334456 KiB
#include<bits/stdc++.h> using namespace std; const int N=2200009; int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,za,seg[N],seg2[N],seg3[N]; char ch; multiset <int> lf[N],rg[N],mn,mx; void up(int q){ if(q==0) return; if(seg[q*2]==-1||seg[q*2+1]==-1){ seg[q]=max(seg[q*2],seg[q*2+1]); }else{ seg[q]=min(seg[q*2],seg[q*2+1]); } seg2[q]=max(seg2[q*2],seg2[q*2+1]); if(seg3[q*2]==-1||seg3[q*2+1]==-1){ seg3[q]=max(seg3[q*2],seg3[q*2+1]); }else{ seg3[q]=min(seg3[q*2],seg3[q*2+1]); } int qw=seg3[q*2+1]-seg2[q*2]; if(qw>0){ if(seg[q]>qw||seg[q]==-1) seg[q]=qw; } up(q/2); } void upd(int q){ multiset <int>::iterator it,tt,zit,ztt; if(lf[q].size()==0||rg[q].size()==0){ seg[q+za-1]=-1; }else{ it=lf[q].end();it--; tt=rg[q].begin(); seg[q+za-1]=(*tt)-(*it); } if(lf[q].size()==0){ seg2[q+za-1]=-1; }else{ it=lf[q].end();it--; seg2[q+za-1]=(*it); } if(rg[q].size()==0){ seg3[q+za-1]=-1; }else{ it=rg[q].begin(); seg3[q+za-1]=(*it); } up((q+za-1)/2); } int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>tes; za=1; while(za<1000000) za*=2; for(i=1; i<=za*2; i++){ seg[i]=-1; seg2[i]=seg3[i]=-1; } for(t=1; t<=tes; t++){ cin>>ch>>c>>d; if(ch=='A'){ lf[d].insert(c); rg[c].insert(d); mn.insert(d); mx.insert(c); }else{ lf[d].erase(lf[d].lower_bound(c)); rg[c].erase(rg[c].lower_bound(d)); mn.erase(mn.lower_bound(d)); mx.erase(mx.lower_bound(c)); } upd(c); upd(d); multiset <int>::iterator it,tt,zit,ztt; it=mn.begin(); tt=mx.end();tt--; if((*tt)<(*it)){ c=(*tt);d=(*it); zit=lf[d].end();zit--; ztt=rg[c].begin(); cout<<(*ztt)-(*zit)<<endl; }else{ cout<<seg[1]<<endl; } } 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...