Submission #1217589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217589		hengliao	Distributing Candies (IOI21_candies)	C++20	29 / 100	134 ms	16868 KiB

candies

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{

    const ll mxN=2e5+5;

    ll pre[mxN];
    ll br[mxN];
    ll v[mxN], c[mxN];
    vector<array<ll, 3>> stk;
    vll con;
    ll timer;

    ll id(ll tar){
        return lower_bound(con.begin(), con.end(), tar)-con.begin();
    }

    ll getsum(ll a, ll b){
        return pre[b+1]-pre[a];
    }

    ll getval(ll idx){
        ll lef=0, rig=stk.size()-1;
        ll good=-1;
        while(lef<=rig){
            ll mid=(lef+rig)/2;
            if(stk[mid][0]>=idx){
                good=mid;
                lef=mid+1;
            }
            else{
                rig=mid-1;
            }
        }
        if(good==-1){
            return pre[timer];
        }
        ll prevbr=stk[good][1];
        ll re=pre[timer]-pre[prevbr+1];
        if(stk[good][2]==1){
            re+=con[idx];
        }
        return re;
    }

}

vector<int> distribute_candies(vector<int> C, vector<int> l,
                            vector<int> r, vector<int> V) {
    ll n = C.size();
    ll q=l.size();
    for(ll i=0;i<n;i++){
        c[i]=C[i];
        con.pb(c[i]);
    }

    pre[0]=0;

    for(ll i=0;i<q;i++){
        v[i]=V[i];
        pre[i+1]=pre[i]+v[i];
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    
    for(ll i=0;i<q;i++){
        timer=i;
        // cout<<"i: "<<i<<'\n';
        // cout<<"stk: "<<'\n';
        // for(auto &it:stk){
        //     cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<'\n';
        // }
        // for(ll j=0;j<(ll) con.size();j++){
        //     cout<<con[j]<<"  val:  "<<getval(j)<<'\n';
        // }
        if(v[i]>0){
            ll lef=0, rig=(ll) con.size()-1;
            ll good=-1;

            auto check=[&](ll tar){
                if(con[tar]-getval(tar)>v[i]){
                    return true;
                }
                return false;
            };

            while(lef<=rig){
                ll mid=(lef+rig)/2;
                if(check(mid)){
                    good=mid;
                    rig=mid-1;
                }
                else{
                    lef=mid+1;
                }
            }

            if(good==-1){
                br[i]=n;
                while(!stk.empty() && stk.back()[0]<=n){
                    stk.pop_back();
                }
                stk.pb({n, i, 1});
            }
            else{
                good--;
                if(good>=0){
                    br[i]=good;
                    while(!stk.empty() && stk.back()[0]<=br[i]){
                        stk.pop_back();
                    }
                    stk.pb({br[i], i, 1});
                }
            }
        }
        else{
            ll lef=0, rig=(ll) con.size()-1;
            ll good=-1;

            auto check=[&](ll tar){
                if(getval(tar)>-v[i]){
                    return true;
                }
                return false;
            };

            while(lef<=rig){
                ll mid=(lef+rig)/2;
                if(check(mid)){
                    good=mid;
                    rig=mid-1;
                }
                else{
                    lef=mid+1;
                }
            }

            if(good==-1){
                br[i]=n;
                while(!stk.empty() && stk.back()[0]<=n){
                    stk.pop_back();
                }
                stk.pb({n, i, 0});
            }
            else{
                good--;
                if(good>=0){
                    br[i]=good;
                    while(!stk.empty() && stk.back()[0]<=br[i]){
                        stk.pop_back();
                    }
                    stk.pb({br[i], i, 0});
                }
                
            }
        }
    }

    timer=q;    

    vll a(n);

    for(ll i=0;i<n;i++){
        a[i]=getval(id(c[i]));
    }

    vector<int> re(n);
    for(ll i=0;i<n;i++){
        re[i]=a[i];
    }
    return re;
}

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