Submission #547066

#TimeUsernameProblemLanguageResultExecution timeMemory
547066leakedFood Court (JOI21_foodcourt)C++14
68 / 100
1086 ms64712 KiB
#include <bits/stdc++.h> #define f first #define s second #define m_p make_pair #define vec vector #define pb push_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define sz(x) (int)(x).size() #define pw(x) (1LL<<(x)) #define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //#define int long long using namespace std; typedef long long ll; const int N=250'000+1; template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} struct fenwick{ ll fnw[N]; fenwick(){ fill(fnw,fnw+N,0); } void reset(){ fill(fnw,fnw+N,0); } void upd(int i,int x){ ++i; while(i<N){ fnw[i]+=x; i+=i&-i; } } ll get(int i){ ++i; ll ans=0; while(i>0){ ans+=fnw[i]; i-=i&-i; } return ans; } void add(int l,int r,ll x){ upd(l,x); upd(r+1,-x); } }; struct segtree{ ll p1[4*N],p2[4*N]; int p3[4*N]; ll mx[4*N],mn[4*N]; segtree(){ fill(mx,mx+4*N,0); fill(mn,mn+4*N,0); fill(p1,p1+4*N,0); fill(p2,p2+4*N,0); fill(p3,p3+4*N,-1); } void push(int v,int tl,int tr){ if(p2[v]!=-1){ // assert(p1[v]==0); for(auto &u : {2*v,2*v+1}){ p2[u]=p2[v]; mx[u]=mn[u]=p2[v]; umax(p3[u],p3[v]); p1[u]=0; } p2[v]=-1; } else{ for(auto &u : {2*v,2*v+1}){ if(p2[u]!=-1) p2[u]+=p1[v]; else p1[u]+=p1[v]; mx[u]+=p1[v];mn[u]+=p1[v]; } p1[v]=0; } } void add(int l,int r,int x,int t,int v,int tl,int tr){ if(tl>r||tr<l) return; if(tl>=l&&tr<=r&&((mx[v]+x)<=0)==((mn[v]+x)<=0)){ // cout<<"TL "<<tl<<' '<<tr<<' '<<mx[v]+x<<' '<<mn[v]+x<<endl; if((mx[v]+x)<=0){ p1[v]=0; umax(p3[v],t); p2[v]=mx[v]=mn[v]=0; // cout<<"WAY "<<v<<' '<<tl<<' '<<tr<<endl; return; } if((p2[v]!=-1)) p2[v]+=x; else p1[v]+=x; mx[v]+=x;mn[v]+=x; return; } int tm=(tl+tr)>>1;push(v,tl,tr); add(l,r,x,t,2*v,tl,tm);add(l,r,x,t,2*v+1,tm+1,tr); mx[v]=max(mx[v<<1],mx[v<<1|1]); mn[v]=min(mn[v<<1],mn[v<<1|1]); } int get(int i,int v,int tl,int tr){ if(tl==tr) return p3[v]; int tm=(tl+tr)>>1;push(v,tl,tr); if(tm>=i) return get(i,v<<1,tl,tm); else return get(i,v<<1|1,tm+1,tr); } }sega; signed main(){ fast_prep; int n,m,q; cin>>n>>m>>q; fenwick fen; vec<int> tl(q),tr(q); vec<int> t(q),l(q),r(q),c(q); vec<ll> k(q); vec<int> ask; vec<ll> rl(q); vec<ll> toadd(q); vec<vec<int>> need(q,vec<int>()); for(int i=0;i<q;i++){ cin>>t[i]; if(t[i]==1){ cin>>l[i]>>r[i]>>c[i]>>k[i]; --l[i];--r[i]; sega.add(l[i],r[i],k[i],i,1,0,n-1); } else if(t[i]==2){ cin>>l[i]>>r[i]>>k[i]; --l[i];--r[i]; fen.add(l[i],r[i],k[i]); sega.add(l[i],r[i],-k[i],i,1,0,n-1); } else{ ask.pb(i); cin>>l[i]>>k[i]; --l[i]; rl[i]=fen.get(l[i])+k[i]; // cerr<<"WO "<<sega.get(l[i],1,0,n-1); tl[i]=sega.get(l[i],1,0,n-1)+1;tr[i]=i; if(tl[i]!=0) need[tl[i]-1].pb(i); } } { fen.reset(); for(int i=0;i<q;i++){ if(t[i]==1) fen.add(l[i],r[i],k[i]); else if(t[i]==2) fen.add(l[i],r[i],-k[i]); for(auto &j : need[i]){ toadd[j]=-fen.get(l[j]); } } } int ok=1; while(ok){ ok=0; fen.reset(); vec<vec<int>> toask(q,vec<int>()); ///just an id for(auto &i : ask){ if(tl[i]!=tr[i]){ int tm=(tl[i]+tr[i])>>1; // cout<<"HEYASK "<<i<<' '<<tl[i]<<' '<<tr[i]<<' '<<tm<<endl; ok=1; toask[tm].pb(i); } } if(!ok) break; for(int i=0;i<q;i++){ if(t[i]==1){ fen.add(l[i],r[i],k[i]); } // cout<<"I "<<i<<endl; for(auto &j : toask[i]){ ll have=fen.get(l[j])+toadd[j]; // cout<<"YO "<<c[i]<<' '<<j<<' '<<have<<' '<<rl[j]<<endl; if(have>=rl[j]){ tr[j]=i; } else{ tl[j]=i+1; } } } } for(auto &i : ask){ cout<<(tl[i]==i?0:c[tl[i]])<<'\n'; } return 0; } /* 3 5 5 1 2 3 5 2 1 1 2 2 4 2 1 3 3 1 2 3 4 2 3 3 2 3 5 5 1 2 3 5 2 1 1 2 2 4 2 1 3 3 3 1 2 1 2 3 4 2 */
#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...