#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
node *l,*r;
int s,e,ad=0,rm=0,rmd=0;//rmd: removed...
node(int ss,int ee){
s=ss;e=ee;
if(s==e){
l=r=NULL;
}else{
l=new node(s,(s+e)/2);
r=new node((s+e)/2+1,e);
}
}
void prop(){
if(l){
l->update(s,e,rm);
l->update(s,e,ad);
l->rmd+=rmd;
}
if(r){
r->update(s,e,rm);
r->update(s,e,ad);
r->rmd+=rmd;
}
rm=ad=rmd=0;
}
void update(int a,int b,int c){
if(a<=s && e<=b){
if(c<0)rmd+=min(ad,-c);
ad+=c;
if(ad<0){
rm+=ad;ad=0;
}
return;
}
prop();
if(a<=(s+e)/2)l->update(a,b,c);
if((s+e)/2<b)r->update(a,b,c);
}
int query(int p,int mn){//query for rmd...
if(s==e){
if(ad<mn)return -1;
return rmd;
}
prop();
if(p<=(s+e)/2)return l->query(p,mn);
else return r->query(p,mn);
}
} *root;
const int inf=LLONG_MAX;
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define pii pair<int,int>
int ans[250005],nex=0;
struct node2{
node2 *l,*r;
int s,e,mm=inf;//mm stores which query is the nearest to being answered...
int val=0;//similar to previous segtree
vector<pii> vv;//value, answer it
node2(int ss,int ee){
s=ss;e=ee;
if(s==e){
l=r=NULL;
}else{
l=new node2(s,(s+e)/2);
r=new node2((s+e)/2+1,e);
}
}
void rev(){
if(l)l->rev();if(r)r->rev();
if(vv.size()>0)sort(vv.begin(),vv.end(),greater<pii>() );//smallest cross value behind...
}
void add(int p,int v,int it){//shop p, cross value v, update answer it...
if(s==e){
vv.eb(v,it);
mm=min(mm,v-val);
return;
}
if(p<=(s+e)/2)l->add(p,v,it);
else r->add(p,v,it);
mm=min(l->mm,r->mm);
}
void join(int a,int b,int cnt,int typ){
if(a<=s && e<=b && cnt<mm){
val+=cnt;
mm-=cnt;
return;
}else if(s==e){
val+=cnt;
while(vv.size()>0 && val>=vv.back().f){
ans[vv.back().s]=typ;
vv.pop_back();
}
mm=inf;
if(vv.size()>0)mm=vv.back().f-val;
return;
}
//prop: since it was left to lazy, nothing should happen...
l->join(s,e,val,-1);
r->join(s,e,val,-1);
val=0;
if(a<=(s+e)/2)l->join(a,b,cnt,typ);
if((s+e)/2<b)r->join(a,b,cnt,typ);
mm=min(l->mm,r->mm);
}
} *r2;
vector<pair<pii,pii> > mm;
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int n,m,q;
cin>>n>>m>>q;
root=new node(1,n);
r2=new node2(1,n);
int a,b,c,d,e;
while(q--){
cin>>a;
if(a==1){//people join the queue...
cin>>b>>c>>d>>e;
mm.eb(mp(b,c),mp(e,d));//range b to c, e customers, type d
root->update(b,c,e);
}else if(a==2){//people leave the queue...
cin>>b>>c>>d;
root->update(b,c,-d);
}else{
cin>>b>>c;//query shop b, cth customer...
e=root->query(b,c);
//cout<<"DEBUG"<<e<<'\n';
if(e==-1)nex++;
else{
ans[nex++]=1;
//c+=e;
//r2->add(b,c,nex++);
}
}
}
/*r2->rev();
for(auto x:mm){
r2->join(x.f.f,x.f.s,x.s.f,x.s.s);
}*/
for(int i=0;i<nex;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
/*
3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
3 3 2
*/
Compilation message
foodcourt.cpp: In member function 'void node2::rev()':
foodcourt.cpp:78:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
78 | if(l)l->rev();if(r)r->rev();
| ^~
foodcourt.cpp:78:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
78 | if(l)l->rev();if(r)r->rev();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
19728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
593 ms |
68192 KB |
Output is correct |
| 2 |
Correct |
456 ms |
57688 KB |
Output is correct |
| 3 |
Correct |
683 ms |
75428 KB |
Output is correct |
| 4 |
Correct |
520 ms |
77796 KB |
Output is correct |
| 5 |
Correct |
530 ms |
60604 KB |
Output is correct |
| 6 |
Correct |
692 ms |
79436 KB |
Output is correct |
| 7 |
Correct |
105 ms |
8516 KB |
Output is correct |
| 8 |
Correct |
111 ms |
8516 KB |
Output is correct |
| 9 |
Correct |
644 ms |
80040 KB |
Output is correct |
| 10 |
Correct |
613 ms |
79952 KB |
Output is correct |
| 11 |
Correct |
672 ms |
78572 KB |
Output is correct |
| 12 |
Correct |
702 ms |
78632 KB |
Output is correct |
| 13 |
Correct |
689 ms |
78556 KB |
Output is correct |
| 14 |
Correct |
681 ms |
78880 KB |
Output is correct |
| 15 |
Correct |
661 ms |
79024 KB |
Output is correct |
| 16 |
Correct |
705 ms |
79008 KB |
Output is correct |
| 17 |
Correct |
694 ms |
78960 KB |
Output is correct |
| 18 |
Correct |
713 ms |
78504 KB |
Output is correct |
| 19 |
Correct |
743 ms |
78604 KB |
Output is correct |
| 20 |
Correct |
727 ms |
78904 KB |
Output is correct |
| 21 |
Correct |
690 ms |
79060 KB |
Output is correct |
| 22 |
Correct |
674 ms |
79092 KB |
Output is correct |
| 23 |
Correct |
687 ms |
79304 KB |
Output is correct |
| 24 |
Correct |
699 ms |
78832 KB |
Output is correct |
| 25 |
Correct |
500 ms |
63276 KB |
Output is correct |
| 26 |
Correct |
563 ms |
79520 KB |
Output is correct |
| 27 |
Correct |
552 ms |
82200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
19552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
