This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const long long maxn=250000+10;
long long n,m,q,res[maxn],kaf=(1<<19);
struct que{
long long 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(long long i){
long long 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(long long i){
long long 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(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return fakenode;
}
if(l>=tl&&r<=tr){
return seg[i];
}
long long m=(l+r)>>1;
return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}seg;
vector<long long>ins[maxn],del[maxn],por[maxn];
void vorod(){
cin>>n>>m>>q;
for(long long 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(long long 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(long long 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 ;
}
long long 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(long long 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(long long 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 (stderr)
foodcourt.cpp: In member function 'void segment::reset(long long int)':
foodcourt.cpp:38:13: warning: unused variable 'fu' [-Wunused-variable]
38 | long long fu=i;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |