Submission #1229488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229488		guagua0407	Distributing Candies (IOI21_candies)	C++20	100 / 100	449 ms	55508 KiB

candies

#include "candies.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int mxn=2e5+5;
    const ll inf=(ll)1e18;
    vector<pair<ll,int>> mx(mxn*4);
    vector<pair<ll,int>> mn(mxn*4);
    vector<ll> lz(mxn*4);
    int n,q;
    void push(int v){
        mx[v*2].f+=lz[v];
        mn[v*2].f+=lz[v];
        lz[v*2]+=lz[v];
        mx[v*2+1].f+=lz[v];
        mn[v*2+1].f+=lz[v];
        lz[v*2+1]+=lz[v];
        lz[v]=0;
    }
    void init(int l=0,int r=q,int v=1){
        if(l==r){
            mx[v]={0,l};
            mn[v]={0,l};
            return;
        }
        int mid=(l+r)/2;
        init(l,mid,v*2);
        init(mid+1,r,v*2+1);
        mx[v]=max(mx[v*2],mx[v*2+1]);
        mn[v]=min(mn[v*2],mn[v*2+1]);
    }
    void update(int tl,int tr,int val,int l=0,int r=q,int v=1){
        if(r<tl or tr<l){
            return;
        }
        if(tl<=l and r<=tr){
            mx[v].f+=val;
            mn[v].f+=val;
            lz[v]+=val;
            return;
        }
        push(v);
        int mid=(l+r)/2;
        update(tl,min(mid,tr),val,l,mid,v*2);
        update(max(tl,mid+1),tr,val,mid+1,r,v*2+1);
        mx[v]=max(mx[v*2],mx[v*2+1]);
        mn[v]=min(mn[v*2],mn[v*2+1]);
    }
    ll get(int pos,int l=0,int r=q,int v=1){
        if(l==r){
            return mx[v].f;
        }
        push(v);
        int mid=(l+r)/2;
        if(pos<=mid) return get(pos,l,mid,v*2);
        else return get(pos,mid+1,r,v*2+1);
    }
    pair<int,int> find(int k,int l=0,int r=q,int v=1,pair<ll,int> mxx={-inf,-1},pair<ll,int> mnn={inf,-1}){
        //cout<<"q "<<l<<' '<<r<<' '<<mn[v].f<<' '<<mx[v].f<<' '<<mnn.f<<' '<<mxx.f<<'\n';
        if(max(mxx,mx[v]).f-min(mnn,mn[v]).f<k){
            //cout<<"pooh"<<'\n';
            return make_pair(-1,-1);
        }
        if(l==r){
            //cout<<"l "<<l<<' '<<min(mnn,mn[v]).s<<' '<<max(mxx,mx[v]).s<<'\n';
            if(min(mnn,mn[v]).s<max(mxx,mx[v]).s) return make_pair(max(mxx,mx[v]).s,1);
            else return make_pair(min(mnn,mn[v]).s,-1);
        }
        push(v);
        int mid=(l+r)/2;
        pair<int,int> res=find(k,mid+1,r,v*2+1,mxx,mnn);
        if(res.f!=-1) return res;
        else return find(k,l,mid,v*2,max(mxx,mx[v*2+1]),min(mnn,mn[v*2+1]));
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> V) {
    n=(int)c.size();
    q=(int)l.size();
    vector<vector<int>> st(n),en(n);
    for(int i=0;i<q;i++){
        st[l[i]].push_back(i);
        en[r[i]].push_back(i);
    }
    init();
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        for(auto v:st[i]){
            update(v+1,q,V[v]);
        }
        {
            pair<int,int> pos=find(c[i]);
            //cout<<i<<' '<<pos.f<<' '<<pos.s<<'\n';
            if(pos.f==-1){
                int p=mn[1].s;
                ans[i]=get(q)-get(p);
            }
            else{
                if(pos.s==1){
                    assert((get(pos.f)-get(q))<=c[i]);
                    ans[i]=max(0ll,c[i]-(get(pos.f)-get(q)));
                }
                else{
                    assert((get(q)-get(pos.f))<=c[i]);
                    ans[i]=max(0ll,(get(q)-get(pos.f)));
                }
            }
            ans[i]=min(c[i],max(0,ans[i]));
        }
        for(auto v:en[i]){
            update(v+1,q,-V[v]);
        }
    }
    return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33