Submission #91811

#TimeUsernameProblemLanguageResultExecution timeMemory
91811SamAndMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
187 ms3192 KiB
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int N=100005,M=1000000000; int t[N*120]; int ll[N*120],rr[N*120]; int z; void ubd(int tl,int tr,int l,int r,int pos) { if(t[pos]==(tr-tl+1)) return; if(tl==l && r==tr) { t[pos]=r-l+1; return; } int m=(tl+tr)/2; if(r<=m) { if(!ll[pos]) ll[pos]=++z; ubd(tl,m,l,r,ll[pos]); } else if(l>m) { if(!rr[pos]) rr[pos]=++z; ubd(m+1,tr,l,r,rr[pos]); } else { if(!ll[pos]) ll[pos]=++z; if(!rr[pos]) rr[pos]=++z; ubd(tl,m,l,m,ll[pos]); ubd(m+1,tr,m+1,r,rr[pos]); } t[pos]=0; if(ll[pos]) t[pos]+=t[ll[pos]]; if(rr[pos]) t[pos]+=t[rr[pos]]; } int qry(int tl,int tr,int l,int r,int pos) { if(t[pos]==(tr-tl+1)) return (r-l+1); if(tl==l && tr==r) return t[pos]; int m=(tl+tr)/2; if(r<=m) { if(!ll[pos]) return 0; return qry(tl,m,l,r,ll[pos]); } else if(l>m) { if(!rr[pos]) return 0; return qry(m+1,tr,l,r,rr[pos]); } else { if(!ll[pos] && !rr[pos]) return 0; else if(ll[pos] && !rr[pos]) return qry(tl,m,l,m,ll[pos]); else if(!ll[pos] && rr[pos]) return qry(m+1,tr,m+1,r,rr[pos]); else return qry(tl,m,l,m,ll[pos])+qry(m+1,tr,m+1,r,rr[pos]); } } int main() { //freopen("f.in","r",stdin); //freopen("f.out","w",stdout); int q; cin>>q; int c=0; while(q--) { int z,x,y; cin>>z>>x>>y; x+=c; y+=c; if(z==1) { int ans=qry(1,M,x,y,0); cout<<ans<<endl; c=ans; } else { ubd(1,M,x,y,0); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...