Submission #1063213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063213		Gray	Distributing Candies (IOI21_candies)	C++17	0 / 100	703 ms	48316 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define ld long double
const ll inf=2e18;

struct segtree{
    struct node{
        ll mn, mx, upd;
        node(){
            mn=0;
            mx=0;
            upd=0;
        }
        void print(){
            cout << "Printing: " << mn << " " << mx << " " << upd << "; ";
        }
        node(ll a, ll b, ll c) : mn(a),mx(b),upd(c){} 
    };
    vector<node> t;
    ll sz, rsz;
    segtree(ll n){
        sz=n*4; rsz=n;
        t.resize(sz);
    }
    void preprocess(ll v, ll tl, ll tr){
        if (t[v].upd){
            // if (t[v].mn<inf) 
                t[v].mn+=t[v].upd;
            // else t[v].mn=t[v].upd;
            // if (t[v].mx>-inf) 
                t[v].mx+=t[v].upd;
            // else t[v].mx=t[v].upd;
            if (tl!=tr) {
                t[v*2].upd+=t[v].upd;
                t[v*2+1].upd+=t[v].upd;
            }
            t[v].upd=0;
        }
    }
    node merge(node l, node r){
        // l.print(); r.print();
        node ret = node(min(l.mn, r.mn), max(l.mx, r.mx), 0ll);
        // cout << "->"; ret.print();
        // cout << ln;
        return ret;
    }
    void update(ll tl, ll tr, ll v, ll l, ll r, ll x){
        if (tl==l and tr==r){
            t[v].upd+=x;
            preprocess(v, tl, tr);
            return;
        }else if (l>r) {preprocess(v, tl, tr);return;}
        preprocess(v, tl, tr);
        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);
    }
    void query(ll l, ll r, ll tl, ll tr, ll v, pair<ll, ll> &res){
        if (tl==l and tr==r){
            preprocess(v, tl, tr);
            res.ff=min(res.ff, t[v].mn);
            res.ss=max(res.ss, t[v].mx);
            return;
        }else if (l>r) {preprocess(v, tl, tr); return;}
        preprocess(v, tl, tr);
        ll tm = (tl+tr)/2;
        query(l, min(tm, r), tl, tm, v*2, res);
        query(max(l, tm+1), r, tm+1, tr, v*2+1, res);
    }
    pair<ll, ll> query(ll l, ll r){
        // if (r==-1) return {0, 0};
        // l=max(l, 0ll);
        assert(l>-1 and r>-1);
        pair<ll, ll> res={inf, -inf};
        query(l, r, 0, rsz-1, 1, res);
        return res;
    }
    void debug(ll tl, ll tr, ll v){
        preprocess(v, tl, tr);
        if (tl==tr){
            cout << (t[v].mn==inf?-1:t[v].mn) << "-" << (t[v].mx==-inf?-1:t[v].mx) << " ";
        }else{
            cout << (t[v].mn==inf?-1:t[v].mn) << "-" << (t[v].mx==-inf?-1:t[v].mx) << "(";
            ll tm=(tl+tr)/2;
            debug(tl, tm, v*2);
            debug(tm+1, tr, v*2+1);
            cout << ") ";
        }
    }
    void debug(){
        debug(0, rsz-1, 1);
        cout << ln;
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    ll n = c.size();
    vector<vector<ll>> start(n), end(n);
    // cout << n << endl;
    l.insert(l.begin(), 0);
    r.insert(r.begin(), n-1);
    v.insert(v.begin(), 0);
    for (ll i=0; i<(ll)l.size(); i++){
        // cout << l[i] << "-" << r[i] << endl;
        start[l[i]].push_back(i);
        end[r[i]].push_back(i);
    }
    segtree tr(n);
    vector<int> res(n);
    for (ll i=0; i<n; i++){
        for (auto j:start[i]){
            // cout << "Hap" << j << ln;
            tr.update(j, n-1, v[j]);
        }
        // tr.debug();
        ll lo=-1, hi=n;
        while (lo+1<hi){
            ll mid = (lo+hi)/2;
            pair<ll, ll> ret=tr.query(mid, n-1);
            if (ret.ss-ret.ff>=c[i]) lo=mid;
            else hi=mid;
        }
        // cout << i << ": " << lo << "::";
        pair<ll, ll> ret = tr.query(max(lo, 0ll), n-1);
        // cout << ret.ff << " " << ret.ss << ln;
        if (lo==-1){
            res[i] = (tr.query(n-1, n-1).ff-ret.ff);
        }else if (tr.query(lo, lo).ff==ret.ff){
            res[i] = c[i]-(ret.ss-tr.query(n-1, n-1).ff);
        }else{
            // cout << "Hap: " << tr.query(n-1, n-1).ff-ret.ff << ln;
            res[i] = (tr.query(n-1, n-1).ff-ret.ff);
        }
        res[i]=min(c[i], max(0, res[i]));
        for (auto j:end[i]){
            tr.update(j, n-1, -v[j]);
        }
    }
    return res;
}

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