Submission #547109

#TimeUsernameProblemLanguageResultExecution timeMemory
547109leakedFood Court (JOI21_foodcourt)C++14
13 / 100
673 ms71508 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 //#pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; const ll inf=1e18; const int N=3e5+1; template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} template<class T> bool umin(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],p4[4*N]; ///add,whom,to_set int p3[4*N]; struct node{ ll x,y; node(){ x=0,y=inf; } }; node mg(node a,node b){ if(a.x>b.x) swap(a.x,b.x); if(b.x>b.y) swap(b.x,b.y); if(a.x==b.x) umin(a.y,b.y); else umin(a.y,b.x); return a; } node tt[4*N]; segtree(){ fill(p1,p1+4*N,0); fill(p2,p2+4*N,-inf); fill(p4,p4+4*N,0); fill(p3,p3+4*N,-1); } void push(int v,int tl,int tr){ // if(p2[v]==-inf && p1[v]==0) // return; for(auto &u : {v<<1,v<<1|1}){ if(tt[u].x==p2[v]){ tt[u].x=p4[v]; umax(p3[u],p3[v]); // p2[u]=p }else tt[u].x+=p1[v]; if(p2[v]!=-inf){ p2[u]=p2[v]; p4[u]=p4[v]; }else p4[u]+=p1[v]; tt[u].y+=p1[v]; p1[u]+=p1[v]; } p1[v]=0;p2[v]=-inf; } bool check(ll a,ll b,ll c){ if((a+c)<=0 && (b+c)<=0) return 0; return 1; } void add(int l,int r,int x,int t,int v,int tl,int tr){ if(tl>r||tr<l) return; // push(v,tl,tr); if(tl>=l&&tr<=r&&check(tt[v].x,tt[v].y,x)){ if((tt[v].x+x)<=0){ p2[v]=(p2[v]==-inf?tt[v].x:p2[v]); umax(p3[v],t); } tt[v].x+=x;tt[v].y+=x; p1[v]+=x;umax(tt[v].x,0LL); p4[v]=tt[v].x; return; } int tm=(tl+tr)>>1;push(v,tl,tr); add(l,r,x,t,v<<1,tl,tm);add(l,r,x,t,v<<1|1,tm+1,tr); tt[v]=mg(tt[2*v],tt[2*v+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); } }sega1; 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]; sega1.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]); sega1.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<<"ALO "<< // cerr<<"WO "<<sega.get(l[i],1,0,n-1); tl[i]=sega1.get(l[i],1,0,n-1)+1;tr[i]=i; // cout<<"ALO "<<tl[i]<<endl; 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]); } } } if(m==1){ 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]==3){ if((fen.get(l[i])+toadd[i])>=rl[i]){ cout<<1<<'\n'; } else{ cout<<0<<'\n'; } } } return 0; } 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...