Submission #602355

#	Time	Username	Problem	Language	Result	Execution time	Memory
602355		rrrr10000	Distributing Candies (IOI21_candies)	C++17	100 / 100	462 ms	46924 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
struct segtree{
    ll n;
    vector<PP> seg;
    segtree(ll n_):n(n_),seg(n_*2){}
    PP f(PP a,PP b){
        chmax(get<1>(a),get<0>(a)+get<1>(b));
        chmin(get<2>(a),get<0>(a)+get<2>(b));
        get<0>(a)+=get<0>(b);
        return a;
    }
    void update(ll i,PP x){
        i+=n;seg[i]=x;
        for(i>>=1;i>0;i>>=1)seg[i]=f(seg[i*2],seg[i*2+1]);
    }
    PP rng(ll l,ll r){
        PP resl(0,0,0),resr(0,0,0);
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1)resl=f(resl,seg[l++]);
            if(r&1)resr=f(seg[--r],resr);
        }
        return f(resl,resr);
    }
    void debug(){
        rep(i,n)cout<<'('<<get<0>(seg[i+n])<<','<<get<1>(seg[i+n])<<','<<get<2>(seg[i+n])<<')';
        cout<<endl;
    }
};
vector<int> distribute_candies(vector<int> C, vector<int> L,vector<int> R, vector<int> V) {
    ll n=C.size(),q=L.size();
    vi c(n),l(q),r(q),v(q);
    rep(i,n)c[i]=C[i];
    rep(i,q)l[i]=L[q-i-1];
    rep(i,q)r[i]=R[q-i-1]+1;
    rep(i,q)v[i]=-V[q-i-1];
    vvi add(n+1),ers(n+1);
    rep(i,q){
        add[l[i]].pb(i);ers[r[i]].pb(i);
    }
    segtree seg(q);
    vector<int> res(n);
    rep(i,n){
        for(ll x:add[i])seg.update(x,PP(v[x],max(0ll,v[x]),min(0ll,v[x])));
        for(ll x:ers[i])seg.update(x,PP(0,0,0));
        // out(c[i]);
        // seg.debug();
        ll ok=0,ng=q+1;
        while(ng-ok>1){
            ll md=(ok+ng)/2;
            auto tmp=seg.rng(0,md);
            if(get<1>(tmp)-get<2>(tmp)>c[i])ng=md;
            else ok=md;
        }
        if(ok==q)res[i]=-get<2>(seg.rng(0,q));
        else if(get<0>(seg.rng(0,ng))<0)res[i]=c[i]-get<1>(seg.rng(0,ng));
        else res[i]=-get<2>(seg.rng(0,ng));
    }
    return res;
}

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