Submission #1248162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248162		damoon	Food Court (JOI21_foodcourt)	C++20	100 / 100	886 ms	77044 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long
typedef pair<ll,ll> pii;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define mid (l+r)/2
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
#define dig(x,d) ((x&(1ll<<d)) > 0)

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}
string pr(bool* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i];return"";}
ostream& operator <<(ostream& out, pii x){out << "("<<x.f<<", "<<x.s<<") ";return out;}

const int L=3e5+10,N = 3e5+1;
const ll inf=1000ll*1000*1000*1000*1000*1000+10;
int n,m,q;
int P[L];
vector<int> A[L];
vector<int> en[L],st[L];
ll rem[L],ans[L];

struct que{
    ll mode,C,l,r,k;
}Q[L];

struct sagi{
    struct node{
        pii mn;
        ll lazy;
        node(){
            mn = pii(inf,inf);
            lazy = 0;
        }
    }t[L<<2];

    void build(int id,int l,int r){
        t[id].lazy = 0;
        if(l+1 == r){
            t[id].mn = pii(0,l);
            return;
        }
        build(lc,l,mid);
        build(rc,mid,r);
        t[id].mn = min(t[lc].mn,t[rc].mn);
    }

    void spread(int id){
        if(rc < L*4){
            t[lc].lazy += t[id].lazy;
            t[rc].lazy += t[id].lazy;
        }
        t[id].mn.f += t[id].lazy;
        t[id].lazy = 0;
    }
    void update(int id,int l,int r,int l2,int r2,ll x){
        spread(id);
        if(l==l2 and r==r2){
            t[id].lazy += x;
            return;
        }
        if(l2 < mid)
            update(lc,l,mid,l2,min(r2,mid),x);
        if(r2 > mid)
            update(rc,mid,r,max(l2,mid),r2,x);
        spread(lc);
        spread(rc);
        t[id].mn = min(t[lc].mn,t[rc].mn);
    }
    pii get(int id,int l,int r,int l2,int r2){
        spread(id);
        if(l==l2 and r==r2)
            return t[id].mn;
        pii ans = pii(inf,inf);
        if(l2 < mid)
            ans = min(ans,get(lc,l,mid,l2,min(r2,mid)));
        if(r2 > mid)
            ans = min(ans,get(rc,mid,r,max(l2,mid),r2));
        return ans;
    }

    void put(int ind, ll x){
        update(1,1,N,ind,ind+1,x-get(1,1,N,ind,ind+1).f);
    }
    
    void Prr(int id,int l,int r){
        spread(id);
        cout<<"node: "<<l<<","<<r<<" --> "<<t[id].mn<<endl;
        if(l+1 == r)
            return;
        Prr(lc,l,mid);
        Prr(rc,mid,r);
        return;
    }
}seg;

struct fen{
    ll sum[L];
    void reset(){
        fill(sum+1,sum+L,0);
    }
    void update(int ind,ll x){
        for(int i=ind ; i<L ; i+=i&-i){
            sum[i] += x;
        }
    }
    ll get(int ind){
        ll ans = 0;
        for(int i=ind ; i>0 ; i-=i&-i){
            ans += sum[i];
        }
        return ans;
    }
}F;

bool cmp(int x,int y){
    return (Q[x].k < Q[y].k); 
}

void update(int x){
    if(P[x] == A[x].size())
        return;
    seg.update(1,1,N,x,x+1,-Q[A[x][P[x]]].k);
    P[x]++;
    if(P[x] < A[x].size())
        seg.update(1,1,N,x,x+1, Q[A[x][P[x]]].k);
    else
        seg.put(x,inf);
}

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>q;
    for(int i=1;i<=q;i++){
        cin>>Q[i].mode;
        if(Q[i].mode == 1){
            cin>>Q[i].l>>Q[i].r>>Q[i].C>>Q[i].k;
            en[Q[i].r].pb(i);
            st[Q[i].l].pb(i);
        }
        if(Q[i].mode == 2){
            cin>>Q[i].l>>Q[i].r>>Q[i].k;
            Q[i].k = -Q[i].k;
        }
        if(Q[i].mode == 3){
            cin>>Q[i].l>>Q[i].k;
            A[Q[i].l].pb(i);
        }
    }

    F.reset();
    for(int i=1;i<=n;i++){
        for(auto x:en[i-1]){
            F.update(x,-Q[x].k);
        }
        for(auto x:st[i]){
            F.update(x, Q[x].k);
        }
        for(auto x:A[i]){
            rem[x] = F.get(x);
        }
    }

    for(int i=1;i<=q;i++){
        if(Q[i].mode == 2){
            en[Q[i].r].pb(i);
            st[Q[i].l].pb(i);
        }
    }

    F.reset();
    seg.build(1,1,N);
    for(int i=1;i<=n;i++){
        for(auto x:en[i-1]){
            seg.update(1,1,N,x,N,-Q[x].k);
            F.update(x,-Q[x].k);
        }
        for(auto x:st[i]){
            seg.update(1,1,N,x,N, Q[x].k);
            F.update(x, Q[x].k);
        }

        for(auto x:A[i]){
            rem[x] -= F.get(x)-min(seg.get(1,1,N,1,x+1).f,0ll);
        }
        /*
        cout<<i<<"  seg: "<<seg.prr()<<endl;
        cout<<"------------------"<<endl;
        */
    }

    for(int i=1;i<=q;i++){
        Q[i].k += rem[i];
    }

    seg.build(1,1,N);
    for(int i=n+1;i<N;i++){
        seg.put(i,inf);
    }
    for(int i=1;i<=n;i++){
        sort(all(A[i]),cmp);
        P[i] = 0;
        if(A[i].size())
            seg.put(i,Q[A[i][0]].k);
        else
            seg.put(i,inf);
    }

    fill(ans+1,ans+q+1,0);
    for(int i=1;i<=q;i++){
        if(Q[i].mode != 1)
            continue;
        seg.update(1,1,N,Q[i].l, Q[i].r+1, -Q[i].k);
        while(true){
            pii d = seg.get(1,1,N,1,N);
            if(d.f > 0)
                break;
            if(i < A[d.s][P[d.s]])
                ans[A[d.s][P[d.s]]] = Q[i].C;
            update(d.s);
        }
    }

    for(int i=1;i<=q;i++){
        if(Q[i].mode == 3){
            cout<<ans[i]<<endl;
        }
    }
}

• 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