#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;
if(l==ll and r==rr){
minsz[v]+=val;
maxsz[v]+=val;
lazy[v]+=val;
}else{
psh(v);
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;
if(l==ll and r==rr and minsz[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;
}
psh(v);
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){
long long res=0;
for(int i=tree[v].size()-1;i>=0 and tree[v][i].tim>=qr;i--){
res+=tree[v][i].k;
}
return res;
}
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);
for(int i=l;i<=r;i++){
// minsz[i]+=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);
for(int i=l;i<=r;i++){
// minsz[i]=max(minsz[i]-s,0LL);
}
}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:160:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
160 | update(1,1,n,l,r,{s,i,t});
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
95324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
95324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
432 ms |
100900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1049 ms |
164496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
95324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
576 ms |
112600 KB |
Output is correct |
| 2 |
Correct |
621 ms |
113600 KB |
Output is correct |
| 3 |
Correct |
668 ms |
114124 KB |
Output is correct |
| 4 |
Correct |
461 ms |
110300 KB |
Output is correct |
| 5 |
Correct |
687 ms |
112828 KB |
Output is correct |
| 6 |
Correct |
858 ms |
116632 KB |
Output is correct |
| 7 |
Correct |
980 ms |
103348 KB |
Output is correct |
| 8 |
Correct |
651 ms |
97104 KB |
Output is correct |
| 9 |
Execution timed out |
1054 ms |
104776 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
95324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
95324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
