Submission #905255

#	Time	Username	Problem	Language	Result	Execution time	Memory
905255		alexander707070	Food Court (JOI21_foodcourt)	C++14	13 / 100	1028 ms	148624 KiB

foodcourt

#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 (stderr)

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});
      |                               ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11