Submission #906697

#	Time	Username	Problem	Language	Result	Execution time	Memory
906697		alexander707070	Food Court (JOI21_foodcourt)	C++14	68 / 100	1109 ms	168732 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 sz[4*MAXN];
pair<long long,long long> lazy[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);
    }
}

pair<long long,long long> merge_lazy(pair<long long,long long> a,pair<long long,long long> b){
    long long c = min(a.second, b.first);
    a.second -= c;
    b.first -= c;
    a.first += b.first;
    a.second += b.second;
    return a;
}

void psh(int v){

    sz[2*v]-=lazy[v].first;
    sz[2*v]=max(0LL,sz[2*v]);
    sz[2*v]+=lazy[v].second;

    sz[2*v+1]-=lazy[v].first;
    sz[2*v+1]=max(0LL,sz[2*v+1]);
    sz[2*v+1]+=lazy[v].second;

    lazy[2*v]=merge_lazy(lazy[2*v],lazy[v]);
    lazy[2*v+1]=merge_lazy(lazy[2*v+1],lazy[v]);

    lazy[v]={0,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){
 
        if(val<0){
            sz[v]=max(0LL,sz[v]+val);
            lazy[v].first+=-val;
        }else{
            sz[v]+=val;
            lazy[v].second+=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);
 
        sz[v]=min(sz[2*v],sz[2*v+1]);
    }
}
 
long long getsz(int v,int l,int r,int pos){
    if(l==r)return sz[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);
            update(1,1,n,l,r,{s,i,t});
        }else if(type==2){
            cin>>l>>r>>s;
            add(1,1,n,l,r,-s);
        }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:153:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
  153 |             update(1,1,n,l,r,{s,i,t});
      |                               ^

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