Submission #816001

#	Time	Username	Problem	Language	Result	Execution time	Memory
816001		alvingogo	Distributing Candies (IOI21_candies)	C++17	100 / 100	392 ms	62532 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

typedef long long ll;
pair<ll,int> operator+(pair<ll,int> a,pair<ll,int> b){
    return {a.fs+b.fs,b.sc};
}
struct no{
    ll sum=0;
    pair<ll,int> mn={0,0},mx={0,0};
    ll ans=0;
};
struct ST{
    vector<no> st;
    void init(int x){
        st.resize(4*x);
        build(0,0,x-1);
    }
    void build(int v,int L,int R){
        if(L==R){
            st[v].mn.sc=st[v].mx.sc=L;
            return;
        }
        int m=(L+R)/2;
        build(2*v+1,L,m);
        build(2*v+2,m+1,R);
        merge(st[v],st[2*v+1],st[2*v+2]);
    }
    void merge(no& v,no& a,no& b){
        v.sum=a.sum+b.sum;
        v.mn=min(b.mn,pair<ll,int>(b.sum,-1)+a.mn);
        v.mx=max(b.mx,pair<ll,int>(b.sum,-1)+a.mx);
        v.ans=max({a.ans,b.ans,(b.sum+a.mx.fs)-b.mn.fs,b.mx.fs-(b.sum+a.mn.fs)});
    }
    void update(int v,int L,int R,int p,int x){
        if(L==R){
            st[v].sum=x;
            st[v].mn.fs=st[v].mx.fs=x;
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,x);
        }
        else{
            update(2*v+2,m+1,R,p,x);
        }
        merge(st[v],st[2*v+1],st[2*v+2]);
    }
    no find(int v,int L,int R,int c,no& a){
        if(L==R){
            no h;
            merge(h,st[v],a);
            return h;
        }
        int m=(L+R)/2;
        no h;
        merge(h,st[2*v+2],a);
        if(h.ans>c){
            return find(2*v+2,m+1,R,c,a);
        }
        else{
            a=h;
            return find(2*v+1,L,m,c,a);
        }
    }
}st;
vector<int> distribute_candies(vector<int> w, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n=w.size();
    vector<int> ans(n);
    int q=l.size()+2;
    st.init(q);
    st.update(0,0,q-1,0,2e9);
    vector<vector<pair<int,int> > > upd(n),del(n);
    for(int i=0;i<q-2;i++){
        upd[l[i]].push_back({i+1,v[i]});
        del[r[i]].push_back({i+1,v[i]});
    }
    for(int i=0;i<n;i++){
        for(auto h:upd[i]){
            st.update(0,0,q-1,h.fs,-h.sc);
        }
        no e;
        e.mn.sc=e.mx.sc=q-1;
        auto d=st.find(0,0,q-1,w[i],e);
        if(d.mx.fs-e.mn.fs>w[i]){
            ans[i]=-e.mn.fs;
        }
        else{
            ans[i]=w[i]-e.mx.fs;
        }
        for(auto h:del[i]){
            st.update(0,0,q-1,h.fs,0);
        }
    }
    return ans;
}

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