#include <bits/stdc++.h>
#define SIZE 250005
#define BT 256*1024*2
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct segtree
{
ll mx[BT],mn[BT],lzy[BT],act[BT];
segtree()
{
for(int i=0;i<BT;i++)
{
mx[i]=0;
mn[i]=0;
lzy[i]=0;
act[i]=0;
}
}
void push(int k,int l,int r)
{
if(l!=r)
{
mx[k*2+1]+=lzy[k];
mn[k*2+1]+=lzy[k];
mx[k*2+2]+=lzy[k];
mn[k*2+2]+=lzy[k];
lzy[k*2+1]+=lzy[k];
lzy[k*2+2]+=lzy[k];
}
lzy[k]=0;
if(act[k]==1)
{
if(l!=r)
{
mx[k*2+1]=0;
mn[k*2+1]=0;
mx[k*2+2]=0;
mn[k*2+2]=0;
act[k*2+1]=1;
act[k*2+2]=1;
}
act[k]=0;
}
}
void inc(int k,int l,int r,int a,int b,int v)
{
if(l>r||l>b||r<a) return;
if(a<=l&&r<=b)
{
mn[k]+=v,mx[k]+=v,lzy[k]+=v;
push(k,l,r);
return;
}
push(k,l,r);
int m=(l+r)/2;
inc(k*2+1,l,m,a,b,v);
inc(k*2+2,m+1,r,a,b,v);
mx[k]=max(mx[k*2+1],mx[k*2+2]);
mn[k]=min(mn[k*2+1],mn[k*2+2]);
}
void dec(int k,int l,int r,int a,int b,int v)
{
if(l>r||l>b||r<a) return;
if(a<=l&&r<=b&&((mn[k]<=v?1:0)==(mx[k]<=v?1:0)))
{
if(mx[k]<=v)
{
mx[k]=0,mn[k]=0,act[k]=1;
}
else
{
mx[k]-=v,mn[k]-=v,lzy[k]-=v;
}
push(k,l,r);
return;
}
push(k,l,r);
int m=(l+r)/2;
dec(k*2+1,l,m,a,b,v);
dec(k*2+2,m+1,r,a,b,v);
mx[k]=max(mx[k*2+1],mx[k*2+2]);
mn[k]=min(mn[k*2+1],mn[k*2+2]);
}
ll query(int k,int l,int r,int i)
{
if(l==r) return mx[k];
push(k,l,r);
int m=(l+r)/2;
if(i<=m) return query(k*2+1,l,m,i);
else return query(k*2+2,m+1,r,i);
}
}seg;
struct segg
{
pair<ll,int> mn[BT];
ll lzy[BT];
segg()
{
for(int i=0;i<BT;i++) mn[i]={1e18,i};
}
void push(int k,int l,int r)
{
if(l!=r)
{
mn[k*2+1].first+=lzy[k];
mn[k*2+2].first+=lzy[k];
lzy[k*2+1]+=lzy[k];
lzy[k*2+2]+=lzy[k];
}
lzy[k]=0;
}
void modify(int k,int l,int r,int i,ll v)
{
if(l==r)
{
mn[k]={v,i};
return;
}
push(k,l,r);
int m=(l+r)/2;
if(i<=m) modify(k*2+1,l,m,i,v);
else modify(k*2+2,m+1,r,i,v);
mn[k]=min(mn[k*2+1],mn[k*2+2]);
}
void update(int k,int l,int r,int a,int b,int v)
{
if(l>r||l>b||r<a) return;
if(a<=l&&r<=b)
{
mn[k].first+=v;
lzy[k]+=v;
push(k,l,r);
return;
}
push(k,l,r);
int m=(l+r)/2;
update(k*2+1,l,m,a,b,v);
update(k*2+2,m+1,r,a,b,v);
mn[k]=min(mn[k*2+1],mn[k*2+2]);
}
}seg1;
int n,m,q,t[SIZE],L[SIZE],k[SIZE],c[SIZE],ans[SIZE],ptr[SIZE];
ll R[SIZE],dat[SIZE],Q[SIZE];
vector<pair<ll,int>> Qs[SIZE];
void updf(int x,int v)
{
for(x++;x<SIZE;x+=x&-x)dat[x]+=v;
}
ll getf(int x)
{
ll r=0;
for(x++;x>0;x-=x&-x)r+=dat[x];
return r;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<q;i++)
{
scanf("%d",&t[i]);
if(t[i]==1)scanf("%d%lld%d%d",&L[i],&R[i],&c[i],&k[i]),--L[i],--R[i];
else if(t[i]==2)scanf("%d%lld%d",&L[i],&R[i],&k[i]),--L[i],--R[i];
else scanf("%d%lld",&L[i],&R[i]),--L[i];
}
for(int i=0;i<q;i++)
{
if(t[i]==1)
{
updf(L[i],k[i]);
updf(R[i]+1,-k[i]);
seg.inc(0,0,n-1,L[i],R[i],k[i]);
}
else if(t[i]==2)
{
seg.dec(0,0,n-1,L[i],R[i],k[i]);
}
else
{
ll tot=getf(L[i]),cur=seg.query(0,0,n-1,L[i]);
Q[i]=(cur>=R[i]?tot-cur+R[i]:-1);
}
}
for(int i=0;i<q;i++) if(t[i]==3&&Q[i]!=-1) Qs[L[i]].push_back({Q[i],i});
for(int i=0;i<n;i++) sort(Qs[i].begin(),Qs[i].end());
for(int i=0;i<n;i++)
{
if(!Qs[i].empty()) seg1.modify(0,0,n-1,i,Qs[i][0].first);
}
for(int i=0;i<q;i++)
{
if(t[i]==1)
{
seg1.update(0,0,n-1,L[i],R[i],-k[i]);
while(seg1.mn[0].first<=0)
{
int id=seg1.mn[0].second;
ans[Qs[id][ptr[id]].second]=c[i];
ptr[id]++;
if(ptr[id]==Qs[id].size()) seg1.modify(0,0,n-1,id,1e18);
else seg1.modify(0,0,n-1,id,Qs[id][ptr[id]].first-Qs[id][ptr[id]-1].first);
}
}
}
for(int i=0;i<q;i++)
{
if(t[i]!=3) continue;
if(Q[i]==-1) printf("0\n");
else printf("%d\n",ans[i]);
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:203:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | if(ptr[id]==Qs[id].size()) seg1.modify(0,0,n-1,id,1e18);
| ~~~~~~~^~~~~~~~~~~~~~~
foodcourt.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d%d%d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
foodcourt.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | scanf("%d",&t[i]);
| ~~~~~^~~~~~~~~~~~
foodcourt.cpp:165:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | if(t[i]==1)scanf("%d%lld%d%d",&L[i],&R[i],&c[i],&k[i]),--L[i],--R[i];
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:166:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | else if(t[i]==2)scanf("%d%lld%d",&L[i],&R[i],&k[i]),--L[i],--R[i];
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:167:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | else scanf("%d%lld",&L[i],&R[i]),--L[i];
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
30932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
30932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
34416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
43808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
30932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
35368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
30932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
30932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
