Submission #1137012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137012		onlk97	Food Court (JOI21_foodcourt)	C++20	100 / 100	290 ms	34840 KiB

foodcourt

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
const int inf=1e9;
int sum[1000010];
pii cnt[1000010];
pii combine(pii a,pii b){
    return {max(b.x,a.x+b.y),a.y+b.y};
}
void update(int id,int tl,int tr,int pos,int val){
    if (tl==tr){
        sum[id]=max(0LL,val);
        cnt[id]={max(0LL,val),val};
        return;
    }
    int tm=(tl+tr)/2;
    if (pos<=tm) update(2*id,tl,tm,pos,val);
    else update(2*id+1,tm+1,tr,pos,val);
    sum[id]=sum[2*id]+sum[2*id+1];
    cnt[id]=combine(cnt[2*id],cnt[2*id+1]);
}
tii query(int id,int tl,int tr,int l,int r){
    if (l>r) return {{0,0},0};
    if (l<=tl&&tr<=r) return {cnt[id],sum[id]};
    int tm=(tl+tr)/2;
    tii lx=query(2*id,tl,tm,l,min(r,tm));
    tii rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return {combine(lx.x,rx.x),lx.y+rx.y};
}
int desc(int id,int tl,int tr,int val){
    if (tl==tr) return tl;
    int tm=(tl+tr)/2;
    if (sum[2*id]>=val) return desc(2*id,tl,tm,val);
    return desc(2*id+1,tm+1,tr,val-sum[2*id]);
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector <pii> event[n+2];
    int sto[q+1];
    for (int i=1; i<=q; i++) sto[i]=0;
    for (int i=1; i<=q; i++){
        int type; cin>>type;
        if (type==1){
            int l,r,c,k; cin>>l>>r>>c>>k;
            sto[i]=c;
            event[l].pb({i,k});
            event[r+1].pb({i,0});
        } else if (type==2){
            int l,r,k; cin>>l>>r>>k;
            event[l].pb({i,-k});
            event[r+1].pb({i,0});
        } else {
            int a,b; cin>>a>>b;
            event[a].pb({i,b+inf});
        }
    }
    for (int i=2; i<=q; i++){
        if (!sto[i]) sto[i]=sto[i-1];
    }
    int ans[q+1];
    for (int i=1; i<=q; i++) ans[i]=-1;
    for (int i=1; i<=n; i++){
        for (pii j:event[i]){
            if (j.y<=inf) update(1,1,q,j.x,j.y);
        }
        for (pii j:event[i]){
            if (j.y<=inf) continue;
            tii gt=query(1,1,q,1,j.x);
            int w=j.y-inf;
            if (max(gt.x.x,gt.x.y)<w){
                ans[j.x]=0;
                continue;
            }
            ans[j.x]=sto[desc(1,1,q,gt.y-max(gt.x.x,gt.x.y)+w)];
        }
    }
    for (int i=1; i<=q; i++){
        if (ans[i]!=-1) cout<<ans[i]<<'\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

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