Submission #1233549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233549		Gray	Distributing Candies (IOI21_candies)	C++17	100 / 100	407 ms	57100 KiB

candies

#include <bits/stdc++.h>
#include <cassert>
#include "candies.h"
#define ll long long
#define ff first
#define ss second
using namespace std;

const ll INF = 2e18;

struct SegTree{
    struct node{
        ll mx, mn, mxi, mni, add;
        node(){
            mx=mn=mxi=mni=add=0;
        }
        node(bool neutral){
            mx=-INF; mn=INF; mxi=-1; mni=-1; add=0;
        }
    };
    vector<node> t; ll rsz;
    SegTree(ll N){
        rsz=N; t.resize(N*4);
        build(0, rsz-1, 1);
    }
    void preprocess(ll tl, ll tr, ll v){
        if (t[v].add){
            t[v].mn+=t[v].add;
            t[v].mx+=t[v].add;
            if (tl!=tr){
                t[v*2].add+=t[v].add;
                t[v*2+1].add+=t[v].add;
            }
            t[v].add=0;
        }
    }
    node merge(node l, node r){
        node nw;
        nw.mxi=(l.mx>=r.mx?l.mxi:r.mxi);
        nw.mni=(l.mn<=r.mn?l.mni:r.mni);
        nw.mx=max(l.mx, r.mx);
        nw.mn=min(l.mn, r.mn);
        return nw;
    }
    void build(ll tl, ll tr, ll v){
        if (tl==tr){
            t[v].mxi=t[v].mni=tl;
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2);
            build(tm+1, tr, v*2+1);
            t[v]=merge(t[v*2], t[v*2+1]);
        }
    }
    void update(ll tl, ll tr, ll v, ll l, ll r, ll x){
        preprocess(tl, tr, v);
        if (tl==l and tr==r){
            t[v].add+=x;
            preprocess(tl, tr, v);
        }else if (l>r) return;
        else{
            ll tm = (tl+tr)/2;
            update(tl, tm, v*2, l, min(r, tm), x);
            update(tm+1, tr, v*2+1, max(l, tm+1), r, x);
            t[v]=merge(t[v*2], t[v*2+1]);
        }
    }
    void update(ll l, ll r, ll x){
        update(0, rsz-1, 1, l, r, x);
    }
    ll queryLeft(ll tl, ll tr, ll v, ll delta, ll smx, ll smn){
        preprocess(tl, tr, v);
        if (tl==tr){
            // cout << tl << " - " << tr << " | " << rsz-1 << " ~ ";
            // cout << delta << " -> " << max(smx, t[v].mx) << " - " << min(smn, t[v].mn) << endl;
            return ((max(smx, t[v].mx)-min(smn, t[v].mn))>=delta?tl:-1);
        }else{
            ll tm = (tl+tr)/2;
            preprocess(tl, tm, v*2);
            preprocess(tm+1, tr, v*2+1);
            if (max(smx, t[v*2+1].mx)-min(smn, t[v*2+1].mn)>=delta) return queryLeft(tm+1, tr, v*2+1, delta, smx, smn);
            else return queryLeft(tl, tm, v*2, delta, max(smx, t[v*2+1].mx), min(smn, t[v*2+1].mn));
        }
    }
    ll queryLeft(ll delta){
        return queryLeft(0, rsz-1, 1, delta, -INF, INF);
    }

    node query(ll tl, ll tr, ll v, ll l, ll r){
        preprocess(tl, tr, v);
        if (tl==l and tr==r){
            return t[v];
        }else if (l>r) return node(0);
        else{
            ll tm = (tl+tr)/2;
            return merge(query(tl, tm, v*2, l, min(r, tm)), query(tm+1, tr, v*2+1, max(l, tm+1), r));
        }
    }
    array<ll, 3> query(ll l, ll r){
        node ret=query(0, rsz-1, 1, l, r);
        return {ret.mni, ret.mxi, ret.mn};
    }
    ll pquery(ll tl, ll tr, ll v, ll i){
        preprocess(tl, tr, v);
        if (tl==tr){
            assert(t[v].mx==t[v].mn);
            return t[v].mx;
        }else{
            ll tm = (tl+tr)/2;
            if (i<=tm) return pquery(tl, tm, v*2, i);
            else return pquery(tm+1, tr, v*2+1, i);
        }
    }
    ll pquery(ll i){
        return pquery(0, rsz-1, 1, i);
    }
    void debug(){
        cout << "Debuggin: " << t[1].mn << " " << t[1].mx << endl;
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q=l.size();
    vector<vector<array<ll, 3>>> sweep(n);
    for (ll i=0; i<q; i++){
        sweep[l[i]].push_back({i+1, v[i], 0});
        sweep[r[i]].push_back({i+1, v[i], 1});
    }
    vector<int> res(n);
    SegTree tr(q+1);
    for (ll i=0; i<n; i++){
        for (auto [j, d, typ]:sweep[i]){
            if (typ==0){
                // cout << j << " + " << d << endl;
                tr.update(j, q, d);
            }
        }
        // tr.debug();
        // cout << "Here" << endl;
        ll ind = tr.queryLeft(c[i]);
        // cout << "Here: " << ind << endl;
        if (ind==-1){
            array<ll, 3> bound = tr.query(0, q);
            res[i] = tr.pquery(q)+abs(bound[2]);
        }else{
            array<ll, 3> bound = tr.query(ind, q);
            // cout << ind << " - " << bound[0] << " & " << bound[1] << "&" << bound[2] << endl;
            if (bound[0]>=bound[1]){
                res[i] = tr.pquery(q)-tr.pquery(bound[0]);
            }else{

                res[i] = tr.pquery(q)-tr.pquery(bound[1])+c[i];
            }
        }
        // cout << "Here" << endl;
        // cout << "not Here" << endl;
        for (auto [j, d, typ]:sweep[i]){
            if (typ==1){
                tr.update(j, q, -d);
            }
        }
    }
    return res;
}

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