#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;
struct event{
int c,tim;
long long k;
};
const long long inf=1e17;
int n,m,q,type,l,r;
long long s,t;
long long minsz[4*MAXN],lazy[4*MAXN],maxsz[4*MAXN];
int c[MAXN];
vector< event > tree[4*MAXN];
vector<long long> pref[4*MAXN];
void update(int v,int l,int r,int ll,int rr,event news){
if(ll>rr)return;
if(l==ll and r==rr){
tree[v].push_back(news);
if(pref[v].empty())pref[v].push_back(news.k);
else pref[v].push_back(pref[v].back()+news.k);
return;
}else{
int tt=(l+r)/2;
update(2*v,l,tt,ll,min(tt,rr),news);
update(2*v+1,tt+1,r,max(tt+1,ll),rr,news);
}
}
void psh(int v){
minsz[2*v]+=lazy[v];
maxsz[2*v]+=lazy[v];
minsz[2*v]=max(minsz[2*v],0LL);
maxsz[2*v]=max(maxsz[2*v],0LL);
minsz[2*v+1]+=lazy[v];
maxsz[2*v+1]+=lazy[v];
minsz[2*v+1]=max(minsz[2*v+1],0LL);
maxsz[2*v+1]=max(maxsz[2*v+1],0LL);
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void add(int v,int l,int r,int ll,int rr,long long val){
if(ll>rr)return;
psh(v);
if(l==ll and r==rr){
minsz[v]+=val;
maxsz[v]+=val;
lazy[v]+=val;
}else{
int tt=(l+r)/2;
add(2*v,l,tt,ll,min(tt,rr),val);
add(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
minsz[v]=min(minsz[2*v],minsz[2*v+1]);
maxsz[v]=max(maxsz[2*v],maxsz[2*v+1]);
}
}
void rem(int v,int l,int r,int ll,int rr,long long val){
if(ll>rr)return;
psh(v);
if(l==ll and r==rr and minsz[v]>=val){
maxsz[v]-=val;
minsz[v]-=val;
lazy[v]-=val;
return;
}
if(l==ll and r==rr and maxsz[v]<val){
minsz[v]=maxsz[v]=0;
lazy[v]=-inf;
return;
}
if(l==r){
minsz[v]=max(minsz[v]-val,0LL);
maxsz[v]=max(maxsz[v]-val,0LL);
}else{
int tt=(l+r)/2;
rem(2*v,l,tt,ll,min(tt,rr),val);
rem(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
minsz[v]=min(minsz[2*v],minsz[2*v+1]);
maxsz[v]=max(maxsz[2*v],maxsz[2*v+1]);
}
}
long long getsz(int v,int l,int r,int pos){
if(l==r)return minsz[v];
psh(v);
int tt=(l+r)/2;
if(pos<=tt)return getsz(2*v,l,tt,pos);
else return getsz(2*v+1,tt+1,r,pos);
}
long long calc(int v,int qr){
if(tree[v].empty())return 0;
int l=-1,r=tree[v].size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(tree[v][tt].tim>=qr){
r=tt;
}else{
l=tt;
}
}
if(r>0)return pref[v].back()-pref[v][r-1];
return pref[v].back();
}
long long howmany(int v,int l,int r,int pos,int qr){
if(l==r){
return calc(v,qr);
}else{
int tt=(l+r)/2;
if(pos<=tt)return howmany(2*v,l,tt,pos,qr) + calc(v,qr);
else return howmany(2*v+1,tt+1,r,pos,qr) + calc(v,qr);
}
}
int bin(int s,long long t){
int l=0,r=q+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(howmany(1,1,n,s,tt)>=t){
l=tt;
}else{
r=tt;
}
}
return c[l];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=q;i++){
cin>>type;
if(type==1){
cin>>l>>r>>s>>t;
c[i]=s;
add(1,1,n,l,r,t);
update(1,1,n,l,r,{s,i,t});
}else if(type==2){
cin>>l>>r>>s;
rem(1,1,n,l,r,s);
}else{
cin>>s>>t;
if(getsz(1,1,n,s)<t)cout<<"0\n";
else cout<<bin(s,getsz(1,1,n,s)-t+1)<<"\n";
}
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:175:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
175 | update(1,1,n,l,r,{s,i,t});
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
95312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
95312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
105796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
149008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
95312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
341 ms |
116932 KB |
Output is correct |
| 2 |
Correct |
342 ms |
118108 KB |
Output is correct |
| 3 |
Correct |
364 ms |
118728 KB |
Output is correct |
| 4 |
Correct |
251 ms |
114864 KB |
Output is correct |
| 5 |
Correct |
315 ms |
117316 KB |
Output is correct |
| 6 |
Correct |
356 ms |
119720 KB |
Output is correct |
| 7 |
Correct |
72 ms |
96080 KB |
Output is correct |
| 8 |
Correct |
79 ms |
95936 KB |
Output is correct |
| 9 |
Correct |
118 ms |
99208 KB |
Output is correct |
| 10 |
Correct |
158 ms |
112876 KB |
Output is correct |
| 11 |
Correct |
214 ms |
118588 KB |
Output is correct |
| 12 |
Correct |
183 ms |
118520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
95312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
95312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
