#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
#define int long long
void maxx(int &a,int b){if(b>a) a=b;}
using ll = long long;
void minn(ll &a,ll b){if(b<a) a=b;}
//int down(const int &id){return id^1;}
//int upd(const int &id){return id;}
const int MAX=250000+4,mod=1e9+7;
const ll inf=1e15+3;
using ii =pair < int , int >;
vector < int > pr[MAX];
vector < ii >ad[MAX];
int C[MAX],K[MAX];
int SS[MAX*4],lz[MAX*4];
int nx,val,n,m,Q,res;
void upd(int id,int l,int r){
if(nx<=l){
//cout<<"add1z1z "<<id<<' '<<l<<' '<<r<<' '<<val<<'\n';
SS[id]+=val;lz[id]+=val;
return;
}
int mid=l+r>>1;
if(lz[id]){
lz[id<<1]+=lz[id];lz[id<<1|1]+=lz[id];
SS[id<<1]+=lz[id];SS[id<<1|1]+=lz[id];
lz[id]=0;
}
if(nx<=mid)upd(id<<1,l,mid);
upd(id<<1|1,mid+1,r);
SS[id]=min(SS[id<<1],SS[id<<1|1]);
}
void get(int id,int l,int r){
if(l==r){
//cout<<"here "<<nx<<' '<<id<<' '<<l<<' '<<r<<' '<<SS[id]<<'\n';
val=SS[id];return;
}
int mid=l+r>>1;
if(lz[id]){
lz[id<<1]+=lz[id];lz[id<<1|1]+=lz[id];
SS[id<<1]+=lz[id];SS[id<<1|1]+=lz[id];
lz[id]=0;
}
if(nx<=mid)get(id<<1,l,mid);
else{
minn(res,SS[id<<1]);
get(id<<1|1,mid+1,r);
}
//SS[id]=min(SS[id<<1],SS[id<<1|1]);
}
void leo(int id,int l,int r){
if(r<=nx){
if(SS[id]>=val) return;
if(l==r) {res=l;return;}
int mid=l+r>>1;
if(lz[id]){
lz[id<<1]+=lz[id];lz[id<<1|1]+=lz[id];
SS[id<<1]+=lz[id];SS[id<<1|1]+=lz[id];
lz[id]=0;
}
if(SS[id<<1|1]>=val) leo(id<<1,l,mid);
else leo(id<<1|1,mid+1,r);
return;
}
int mid=l+r>>1;
if(lz[id]){
lz[id<<1]+=lz[id];lz[id<<1|1]+=lz[id];
SS[id<<1]+=lz[id];SS[id<<1|1]+=lz[id];
lz[id]=0;
}
if(nx<=mid)leo(id<<1,l,mid);
else{
leo(id<<1|1,mid+1,r);
if(!res) leo(id<<1,l,mid);
}
//SS[id]=min(SS[id<<1],SS[id<<1|1]);
}
void upd(int x){
nx=x;val=K[x];//cout<<"upd "<<x<<' '<<K[x]<<'\n';
K[x]=-K[x];
upd(1,1,Q);
}
void get2(int x){
nx=x;
get(1,1,n);//cout<<val<<'\n';
}
int get(int x,int lim){
//cout<<x<<' '<<lim<<'\n';
nx=x;res=inf;
get(1,1,Q);
//cout<<val<<' '<<res<<'\n';
if(val-res<lim) return 0;
val=res+lim;res=0;
leo(1,1,Q);
return C[res+1];
}
int ans[MAX];
signed main(){
///g++ grader.cpp .cpp -std=c++14 -O2 -Wl,--stack,10485760
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("JOI21_foodcourt.inp","r",stdin);//freopen("JOI21_foodcourt.out","w",stdout);
cin>>n>>m>>Q;
for(int i=1,t,x,y;i<=Q;i++){
cin>>t>>x>>y;
if(t==3)ad[x].pb(ii(i,y));
else{
ans[i]=-1;
if(t==1){
cin>>C[i]>>K[i];
pr[x].pb(i);
pr[y+1].pb(i);
}
else{
cin>>K[i];K[i]=-K[i];
pr[x].pb(i);
pr[y+1].pb(i);
}
}
}
for(int i=1;i<=n;i++){
for(int u:pr[i])
upd(u);
for(ii u:ad[i]){
ans[u.X]=get(u.X,u.Y);
//return 0;
//leo()
///continue bae
}
}
for(int i=1;i<=Q;i++) if(ans[i]!=-1)cout<<ans[i]<<'\n';
}
Compilation message
foodcourt.cpp: In function 'void upd(long long int, long long int, long long int)':
foodcourt.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid=l+r>>1;
| ~^~
foodcourt.cpp: In function 'void get(long long int, long long int, long long int)':
foodcourt.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid=l+r>>1;
| ~^~
foodcourt.cpp: In function 'void leo(long long int, long long int, long long int)':
foodcourt.cpp:60:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid=l+r>>1;
| ~^~
foodcourt.cpp:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
19136 KB |
Output is correct |
| 2 |
Correct |
66 ms |
19188 KB |
Output is correct |
| 3 |
Correct |
69 ms |
19092 KB |
Output is correct |
| 4 |
Correct |
63 ms |
19152 KB |
Output is correct |
| 5 |
Correct |
96 ms |
19236 KB |
Output is correct |
| 6 |
Correct |
67 ms |
19148 KB |
Output is correct |
| 7 |
Correct |
31 ms |
17736 KB |
Output is correct |
| 8 |
Correct |
34 ms |
17564 KB |
Output is correct |
| 9 |
Correct |
61 ms |
18932 KB |
Output is correct |
| 10 |
Correct |
65 ms |
19204 KB |
Output is correct |
| 11 |
Correct |
70 ms |
19108 KB |
Output is correct |
| 12 |
Correct |
86 ms |
19204 KB |
Output is correct |
| 13 |
Incorrect |
71 ms |
18400 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
39420 KB |
Output is correct |
| 2 |
Correct |
248 ms |
35588 KB |
Output is correct |
| 3 |
Correct |
365 ms |
41028 KB |
Output is correct |
| 4 |
Correct |
296 ms |
35836 KB |
Output is correct |
| 5 |
Incorrect |
252 ms |
35756 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
19148 KB |
Output is correct |
| 2 |
Correct |
86 ms |
19600 KB |
Output is correct |
| 3 |
Incorrect |
72 ms |
19660 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
