Submission #560458

#	Time	Username	Problem	Language	Result	Execution time	Memory
560458		kartel	Distributing Candies (IOI21_candies)	C++17	38 / 100	540 ms	57564 KiB

candies

#include <bits/stdc++.h>

//#include "grader.cpp"
#include "candies.h"

#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;

struct st_beats {
    struct node {
        ll mx, mn;
        ll D, Dx;

        node() {
            mx = mn = D = 0;
            Dx = -2e9;
        }

        node operator +(node other) {
            node ret;

            ret.mx = max(mx, other.mx);
            ret.mn = min(mn, other.mn);
            return ret;
        }

        void mrg(node &a, node &b) {
            node x = a + b;
            mx = x.mx; mn = x.mn;
        }

        void add() {
            mx += D; mn += D;
        }

        void updL() {
            mx = mn = Dx;
            Dx = -2e9;
        }
    };

    vector <node> t;
    int n, h;

    st_beats() {}

    void init(int _n, int _h) {
        t.resize(8 * _n);
        for (int i = 0; i < sz(t); i++) {
            t[i] = node();
        }
        h = _h;
        n = _n;
    }

    void push(int v) {
        if (t[v].D) {
            t[v].add();
            t[v * 2].D += t[v].D;
            t[v * 2 + 1].D += t[v].D;
            t[v].D = 0;
        }
    }

    void pushL(int v) {
        if (t[v].Dx != -2e9) {
            t[v * 2].Dx = t[v].Dx;
            t[v * 2 + 1].Dx = t[v].Dx;
            t[v * 2].D = t[v * 2 + 1].D = 0;

            t[v].updL();
        }
    }

    void psh(int v) {
        pushL(v);
        push(v);
    }

    void upd(int v, int l, int r, int tl, int tr, int val) {
        psh(v);
        if (l > r || tl > tr || tl > r || l > tr) {
            return;
        }
        int md = (l + r) >> 1;
        if (l >= tl && r <= tr) {
            t[v].D += val;
            psh(v);
            return;
        }
        upd(v * 2, l, md, tl, tr, val);
        upd(v * 2 + 1, md + 1, r, tl, tr, val);
        t[v].mrg(t[v * 2], t[v * 2 + 1]);
    }

    void upd(int v, int l, int r, int x) {
        psh(v);

        if (t[v].mn > h) {
            t[v].Dx = h;
            psh(v);
            return;
        }
        if (t[v].mx < 0) {
            t[v].Dx = 0;
            psh(v);
            return;
        }

        if (l == r || (t[v].mn >= 0 && t[v].mx <= h)) {
            return;
        }

        int md = (l + r) >> 1;
        upd(v * 2, l, md, 0);
        upd(v * 2 + 1, md + 1, r, 0);
        t[v].mrg(t[v * 2], t[v * 2 + 1]);
    }

    void upd(int l, int r, int val) {
        upd(1, 0, n - 1, l, r, val);

        upd(1, 0, n - 1, 0);
    }

    int get(int v, int l, int r, int ps) {
        psh(v);
        if (l == r) {
            return t[v].mx;
        } else {
            int md = (l + r) >> 1;
            if (ps <= md) {
                return get(v * 2, l, md, ps);
            }
            return get(v * 2 + 1, md + 1, r, ps);
        }
    }

    int get(int x) {
        return get(1, 0, n - 1, x);
    }
} stb;

struct st_min {
    vector <ll> t;
    int n;

    st_min() {}

    void build(int v, int l, int r, vector <ll> &a) {
        if (l == r) {
            t[v] = abs(a[l]);
            return;
        } else {
            int md = (l + r) >> 1;
            build(v * 2, l, md, a);
            build(v * 2 + 1, md + 1, r, a);
            t[v] = min(t[v * 2], t[v * 2 + 1]);
        }
    }

    void init(vector <ll> &a) {
        n = sz(a);
        t.resize(8 * n);
        build(1, 0, n - 1, a);
    }

    void upd(int v, int l, int r, int ps, ll val) {
        if (l == r) {
            t[v] = val;
            return;
        } else {
            int md = (l + r) >> 1;
            if (ps <= md) {
                upd(v * 2, l, md, ps, val);
            } else {
                upd(v * 2 + 1, md + 1, r, ps, val);
            }
            t[v] = min(t[v * 2], t[v * 2 + 1]);
        }
    }

    int get(int v, int l, int r, ll c) {
        if (t[v] >= c) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int md = (l + r) >> 1;
        int cur = get(v * 2, l, md, c);
        if (cur == -1) {
            return get(v * 2 + 1, md + 1, r, c);
        }
        return cur;
    }

    void upd(int ps, ll val) {
        upd(1, 0, n - 1, ps, val);
    }

    int get(ll c) {
        return get(1, 0, n - 1, c);
    }
};

vector <int> solve_st_beats(vector <int> &c, vector <int> &l, vector <int> &r, vector <int> &v) {
    int n = sz(c), q = sz(l);

    stb.init(n, c[0]);
    for (int i = 0; i < q; i++) {
        stb.upd(l[i], r[i], v[i]);
    }

    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = stb.get(i);
    }

    return a;
}

vector <int> solve_offline(vector <int> &c, vector <int> &l, vector <int> &r, vector <int> &v) {
    vector <ll> p = {v[0]};
    int q = sz(l), n = sz(c);
    vector <int> nxt(q, 0);
    set <pair <int, ll> > se;

    auto sg = [&](ll x) {
        if (x < 0) {
            return -1;
        }
        return 1;
    };

    for (int i = 1; i < q; i++) {
        if (sg(p.back()) == sg(v[i])) {
            p.back() += v[i];
        } else {
            p.pb(v[i]);
        }
    }
    if (p[0] < 0) {
        p.erase(p.begin());
    }
    q = sz(p);
    for (int i = 0; i < q; i++) {
        nxt[i] = i + 1;
        se.insert({i, p[i]});
    }

    vector <int> ind(n, 0);
    iota(all(ind), 0);
    sort(all(ind), [&](int i, int j) {return (c[i] < c[j]);});

    st_min tM;
    tM.init(p);

    vector <int> ans(n, 0);
    for (auto i : ind) {
        ll x = c[i];
//        cerr << x << el;
        int j = tM.get(x);
        while (j != -1) {
            ll new_val = p[j], shift = 0;
            if (new_val < 0) {
                shift = x;
            }
            int was = j;
            se.erase({j, p[j]});
            vector <int> pos;
            while (nxt[j] < q && shift + new_val >= 0 && shift + new_val <= x) {
                j = nxt[j];
                pos.pb(j);
                se.erase({j, p[j]});
                new_val += p[j];
                p[j] = 0;
            }
            for (auto k : pos) {
                nxt[k] = nxt[j];
                tM.upd(k, 2e18);
            }
            nxt[was] = nxt[j];
            auto it = se.lower_bound(make_pair(j, 0));
            if (it != se.begin()) {
                --it;
                if (sg(it -> S) == sg(new_val)) {
                    new_val += it -> S;
                    nxt[it -> F] = nxt[j];
                    p[was] = 0;
                    p[it -> F] = new_val;
                    tM.upd(was, 2e18);
                    tM.upd(it -> F, abs(new_val));
                    was = it -> F;

                    se.erase(it);
                    se.insert({was, new_val});
                } else {
                    p[was] = new_val;
                    se.insert({was, new_val});
                    tM.upd(was, abs(new_val));
                }
            } else {
                p[was] = new_val;
                se.insert({was, new_val});
                tM.upd(was, abs(new_val));
            }
            if (nxt[j] == q) {
                break;
            }
            j = tM.get(x);
        }
        ll val = se.rbegin() -> S;
        if (val < 0) {
            if (se.rbegin() -> F) {
                ans[i] = max(0ll, x + val);
            } else {
                ans[i] = 0;
            }
        } else {
            ans[i] = min(x, val);
        }
//        for (int j = 0; j < q; j++) {
//            cerr << p[j] << " ";
//        }
//        cerr << el;
    }

    return ans;
}

vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v) {
    int n = sz(c), q = sz(l);

    if (n <= 2000 && q <= 2000) {
        vector <int> a(n, 0);

        for (int i = 0; i < q; i++) {
            for (int j = l[i]; j <= r[i]; j++) {
                a[j] += v[i];

                a[j] = max(a[j], 0);
                a[j] = min(a[j], c[j]);
            }
        }
        return a;
    } else {
        bool g = 1;
        for (int i = 0; i < q; i++) {
            g &= (v[i] > 0);
        }

        if (g) {
            vector <ll> pf(n, 0);
            vector <int> a(n, 0);

            for (int i = 0; i < q; i++) {
                pf[l[i]] += v[i];
                if (r[i] + 1 < n) {
                    pf[r[i] + 1] -= v[i];
                }
            }

            for (int i = 1; i < n; i++) {
                pf[i] += pf[i - 1];
            }
            for (int i = 0; i < n; i++) {
                a[i] = min(max(0ll, pf[i]), (ll)c[i]);
            }

            return a;
        } else {
            bool eq_c = 1;

            for (int i = 1; i < n; i++) {
                eq_c &= (c[i] == c[0]);
            }

            if (eq_c) {
                return solve_st_beats(c, l, r, v);
            }
            return solve_offline(c, l, r, v);
        }
    }
}

/*

10
99 5 25 85 6 20 41 83 87 87
10
0 9 -17
0 9 21
0 9 31
0 9 -25
0 9 -18
0 9 50
0 9 -41
0 9 -43
0 9 14
0 9 -25
63 0 14 49 0 9 30 47 51 51
0 0 0 0 0 0 0 0 0 0

10
75 24 49 95 80 40 28 41 85 57
10
0 9 -48
0 9 -15
0 9 20
0 9 44
0 9 43
0 9 39
0 9 -49
0 9 -16
0 9 -36
0 9 45
45 24 45 45 45 40 28 41 45 45

10
82 85 7 36 68 4 90 93 32 14
10
0 9 16
0 9 -6
0 9 47
0 9 3
0 9 -36
0 9 6
0 9 41
0 9 -27
0 9 -24
0 9 -12
8 8 0 0 5 0 8 8 0 0

10
55 26 63 57 58 10 89 91 45 72
10
0 9 90
0 9 -37
0 9 87
0 9 35
0 9 26
0 9 -52
0 9 -30
0 9 77
0 9 -87
0 9 45
45 26 45 45 45 10 45 45 45 45
*/

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