Submission #1012920

#TimeUsernameProblemLanguageResultExecution timeMemory
1012920imarnFood Court (JOI21_foodcourt)C++14
100 / 100
360 ms52832 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") #define ll long long #define pii pair<ll,ll> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vl vector<ll> #define vvi vector<vi> using namespace std; const int mxn=250005; struct fenw{ ll a[mxn]{0}; void add(int i,ll amt){ for(;i<mxn;i+=i&-i)a[i]+=amt; } ll qr(int l,int r,ll res=0){ for(;r;r-=r&-r)res+=a[r]; for(l--;l;l-=l&-l)res-=a[l]; return res; } }fw[2]; struct lazy{ pll t[4*mxn];ll lz[4*mxn]{0}; void build(int i,int l,int r){ if(l==r)return void(t[i]={0,l}); int m=(l+r)>>1; build(2*i,l,m);build(2*i+1,m+1,r); t[i]=min(t[2*i],t[2*i+1]); } void push(int i,int l,int r){ t[i].f+=lz[i]; if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i]; lz[i]=0; } void upd(int i,int l,int r,int tl,int tr,ll v){ push(i,l,r); if(r<tl||l>tr)return; if(r<=tr&&l>=tl){ lz[i]+=v;push(i,l,r);return; }int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v); t[i]=min(t[2*i],t[2*i+1]); } pll qr(int i,int l,int r,int tl,int tr){ push(i,l,r); if(r<tl||l>tr)return {1e18,1e18}; if(r<=tr&&l>=tl)return t[i]; int m=(l+r)>>1; return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr)); } }sg; int g[mxn];vector<pair<int,pii>>vec[mxn];vector<pii>ask[mxn]; int ans[mxn]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll n,m,q;cin>>n>>m>>q; for(int i=1;i<=q;i++){ int t;cin>>t; if(t==1){ll l,r,k;cin>>l>>r>>g[i]>>k;vec[l].pb({0,{i,k}}),vec[r+1].pb({0,{i,-k}});} else if(t==2){ll l,r,k;cin>>l>>r>>k;vec[l].pb({1,{i,k}}),vec[r+1].pb({1,{i,-k}});} else {ll a,b;cin>>a>>b;ask[a].pb({b,i});} }sg.build(1,0,q);for(int i=1;i<=q;i++)ans[i]=-1; for(int i=1;i<=n;i++){ for(auto it : vec[i]){ if(it.f==0){sg.upd(1,0,q,it.s.f,q,it.s.s);fw[0].add(it.s.f,it.s.s);} else {sg.upd(1,0,q,it.s.f,q,-it.s.s);fw[1].add(it.s.f,it.s.s);} } for(auto it : ask[i]){ int st=sg.qr(1,0,q,0,it.s).s;st++;ll tt=it.f+fw[1].qr(st,it.s); if(fw[0].qr(st,it.s)<tt){ans[it.s]=0;continue;} int l=st,r=it.s; while(l<r){ int md=(l+r)>>1; if(fw[0].qr(st,md)>=tt)r=md; else l=md+1; }ans[it.s]=g[l]; } } for(int i=1;i<=q;i++)if(ans[i]!=-1)cout<<ans[i]<<'\n'; }
#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...