#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){
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);
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:176:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
176 | update(1,1,n,l,r,{s,i,t});
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
95412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
95412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1025 ms |
105604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1028 ms |
148624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
95412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
349 ms |
117228 KB |
Output is correct |
| 2 |
Correct |
376 ms |
118072 KB |
Output is correct |
| 3 |
Correct |
386 ms |
118892 KB |
Output is correct |
| 4 |
Correct |
243 ms |
114836 KB |
Output is correct |
| 5 |
Correct |
298 ms |
117480 KB |
Output is correct |
| 6 |
Correct |
355 ms |
119664 KB |
Output is correct |
| 7 |
Correct |
66 ms |
96080 KB |
Output is correct |
| 8 |
Correct |
90 ms |
95824 KB |
Output is correct |
| 9 |
Correct |
123 ms |
99140 KB |
Output is correct |
| 10 |
Correct |
140 ms |
112868 KB |
Output is correct |
| 11 |
Correct |
206 ms |
118524 KB |
Output is correct |
| 12 |
Correct |
212 ms |
118448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
95412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
95412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
