#include<bits/stdc++.h>
using namespace std;
const int maxn=250000+10;
int n,m,q,res[maxn],kaf=(1<<19);
struct que{
int l,r,t,k,c;
}allq[maxn];
struct node{
long long summanf,begol,kamkon;
node(){
summanf=begol=kamkon=0;
}
}fakenode;
struct segment{
node seg[(1<<20)];
node merge(node a,node b){
node ret;
ret.summanf=a.summanf+b.summanf;
ret.begol=b.begol+max(0ll,a.begol-b.kamkon);
ret.kamkon=a.kamkon+max(0ll,b.kamkon-a.begol);
return ret;
}
void ins(int i){
int fu=i;
i+=kaf;
if(allq[fu].t==1){
seg[i].begol=allq[fu].k;
}else{
seg[i].summanf=seg[i].kamkon=allq[fu].k;
}
i>>=1;
while(i>0){
seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
void reset(int i){
int fu=i;
i+=kaf;
seg[i].summanf=seg[i].kamkon=seg[i].begol=0;
i>>=1;
while(i>0){
seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
node pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return fakenode;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}seg;
vector<int>ins[maxn],del[maxn],por[maxn];
void vorod(){
cin>>n>>m>>q;
for(int i=1;i<=q;i++){
cin>>allq[i].t;
if(allq[i].t==1){
cin>>allq[i].l>>allq[i].r>>allq[i].c>>allq[i].k;
}else if(allq[i].t==2){
cin>>allq[i].l>>allq[i].r>>allq[i].k;
}else{
cin>>allq[i].l>>allq[i].k;
}
}
}
void pre(){
for(int i=1;i<=q;i++){
if(allq[i].t==1){
ins[allq[i].l].push_back(i);
del[allq[i].r+1].push_back(i);
}else if(allq[i].t==2){
ins[allq[i].l].push_back(i);
del[allq[i].r+1].push_back(i);
}else{
por[allq[i].l].push_back(i);
}
}
}
void pors(int ind){
node unnow=seg.pors(1,0,kaf-1,0,ind);
//cout<<"wtf: "<<ind<<" "<<unnow.begol<<" "<<unnow.kamkon<<endl;
if(unnow.begol<allq[ind].k){
res[ind]=0;
return ;
}
int low=-1,high=ind,mid;
while(high-low>1){
mid=(high+low)>>1;
unnow=seg.pors(1,0,kaf-1,0,mid);
node bad=seg.pors(1,0,kaf-1,mid+1,ind);
if(unnow.begol-bad.summanf>=allq[ind].k){
high=mid;
}else{
low=mid;
}
}
res[ind]=allq[high].c;
}
void solve(){
for(int i=1;i<=n;i++){
for(auto x:del[i]){
seg.reset(x);
}
for(auto x:ins[i]){
seg.ins(x);
}
for(auto x:por[i]){
pors(x);
}
}
}
void khor(){
for(int i=1;i<=q;i++){
if(allq[i].t==3){
cout<<res[i]<<"\n";
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
khor();
}
Compilation message
foodcourt.cpp: In member function 'void segment::reset(int)':
foodcourt.cpp:38:7: warning: unused variable 'fu' [-Wunused-variable]
38 | int fu=i;
| ^~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:135:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | freopen("inp.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
43612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
43612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
43612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
