Submission #421818

#TimeUsernameProblemLanguageResultExecution timeMemory
421818tqbfjotldFood Court (JOI21_foodcourt)C++14
7 / 100
1075 ms113672 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct node{ int s,e; int lazymin,lazych; int v; node *l,*r; node (int _s, int _e){ s = _s; e = _e; lazymin = 0; lazych = 0; v = 0; if (s!=e){ l = new node(s,(s+e)/2); r = new node((s+e)/2+1,e); } } void proc(){ if (lazymin==0 && lazych==0) return; if (s!=e){ l->lazymin = min(l->lazymin,l->lazych+lazymin); l->lazych += lazych; r->lazymin = min(r->lazymin,r->lazych+lazymin); r->lazych += lazych; } if (s==e){ v += lazymin; v = max(v,0LL); v -= lazymin; v += lazych; } lazymin = 0; lazych = 0; } void inc(int a, int b, int val){ proc(); if (a<=s && e<=b){ lazych += val; proc(); return; } else if (b<=(s+e)/2){ l->inc(a,b,val); } else if (a>(s+e)/2){ r->inc(a,b,val); } else{ l->inc(a,b,val); r->inc(a,b,val); } l->proc(); r->proc(); } void dec(int a, int b, int val){ proc(); if (a<=s && e<=b){ lazych -= val; lazymin = min(lazymin,lazych); proc(); return; } else if (b<=(s+e)/2){ l->dec(a,b,val); } else if (a>(s+e)/2){ r->dec(a,b,val); } else{ l->dec(a,b,val); r->dec(a,b,val); } l->proc(); r->proc(); } int qu(int pos){ proc(); if (s==e) return v; if (pos>(s+e)/2)return r->qu(pos); else return l->qu(pos); } }*root; struct q_dat{ int l,r; int t,k; q_dat(){ l = 0; r = 0; t = 0; k = 0; } q_dat(int _l, int _r, int _t, int _k){ l = _l; r = _r; t = _t; k = _k; } }; vector<q_dat> query1; int groupnum[250005]; vector<q_dat> query2; vector<pair<pair<int,int>,int> > query3; int fw[250005]; void upd(int pos, int val){ while (pos<250005){ fw[pos] += val; pos+=pos&-pos; } } int qu(int pos){ int ans = 0; while (pos>0){ ans += fw[pos]; pos -= pos&-pos; } return ans; } int numt[250005]; int ans[250005]; vector<pair<pair<int,int>,int> > bsvals[250005]; vector<pair<pair<int,int>,int> > bsvals2[250005]; struct node2{ int s, e; int lazyval; node2 *l,*r; node2 (int _s, int _e){ s = _s; e = _e; lazyval = -1; if (s!=e){ l = new node2(s,(s+e)/2); r = new node2((s+e)/2+1,e); } } void proc(){ if (lazyval==-1) return; if (s!=e){ l->lazyval = lazyval; r->lazyval = lazyval; lazyval = -1; } } int qu(int pos){ proc(); if (s==e) return lazyval; if (pos<=(s+e)/2) return l->qu(pos); return r->qu(pos); } void upd(int a, int b, int val){ proc(); if (a<=s && e<=b) { lazyval = val; proc(); return; } if (b<=(s+e)/2){ l->upd(a,b,val); } else if (a>(s+e)/2){ r->upd(a,b,val); } else{ l->upd(a,b,val); r->upd(a,b,val); } } }*root2; int incl[250005]; int incr[250005]; int incamt[250005]; int finans[250005]; main(){ int n,m,q; scanf("%lld%lld%lld",&n,&m,&q); root = new node(1,n); for (int x = 0; x<q; x++){ int a; scanf("%lld",&a); if (a==1){ int b,c,d,e; scanf("%lld%lld%lld%lld",&b,&c,&d,&e); groupnum[x] = d; query1.push_back(q_dat(b,c,x,e)); root->inc(b,c,e); upd(b,e); upd(c+1,-e); incl[x] = b; incr[x] = c; incamt[x] = e; } else if (a==2){ int b,c,d; scanf("%lld%lld%lld",&b,&c,&d); query2.push_back(q_dat(b,c,x,d)); root->dec(b,c,d); } else if (a==3){ int b,c; scanf("%lld%lld",&b,&c); query3.push_back({{b,c},x}); int num = root->qu(b); numt[x] = qu(b)-num+c; incl[x] = b; if (num<c){ ans[x] = -1; } //printf("%lld has %lld\n",b,numpopped[x]); } } for (auto x : query3){ if (ans[x.second]==-1) continue; int a = -1; int b = q-1; int mid = (a+b)/2; bsvals[mid].push_back({{a,b},x.second}); } bool found = true; while (found){ found = false; for (int k = 0; k<250005; k++){ fw[k] = 0; } for (int t = 0; t<q; t++){ if (incamt[t]!=0){ upd(incl[t],incamt[t]); upd(incr[t]+1,-incamt[t]); } for (auto x : bsvals[t]){ if (x.first.first+1==x.first.second) { ans[x.second] = x.first.second; continue; } if (qu(incl[x.second])>=numt[x.second]){ bsvals2[(x.first.first+t)/2].push_back({{x.first.first,t},x.second}); } else{ bsvals2[(x.first.second+t)/2].push_back({{t,x.first.second},x.second}); } found = true; } bsvals[t].clear(); } swap(bsvals2,bsvals); } root2 = new node2(1,n); vector<pair<pair<int,int>,int> > stuff; for (auto x : query3){ if (ans[x.second]==-1) { continue; } stuff.push_back({{ans[x.second],incl[x.second]},x.second}); } sort(stuff.begin(),stuff.end()); int curt = 0; for (auto x : stuff){ while (curt<=x.first.first){ if (incamt[curt]!=0){ root2->upd(incl[curt],incr[curt],curt); //printf("set %lld to %lld with %lld\n",incl[curt],incr[curt],curt); } curt++; } finans[x.second] = root2->qu(x.first.second); //printf("query %lld = %lld\n",x.first.second,finans[x.second]); } for (auto x : query3){ // printf("ans = %lld\n",ans[x.second]); if (finans[x.second]==0){ printf("0\n"); } else printf("%lld\n",groupnum[finans[x.second]]); } }

Compilation message (stderr)

foodcourt.cpp:173:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  173 | main(){
      | ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |     scanf("%lld%lld%lld",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~
foodcourt.cpp:182:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |             scanf("%lld%lld%lld%lld",&b,&c,&d,&e);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:194:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |             scanf("%lld%lld%lld",&b,&c,&d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |             scanf("%lld%lld",&b,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
#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...