Submission #560369

#	Time	Username	Problem	Language	Result	Execution time	Memory
560369		kartel	Distributing Candies (IOI21_candies)	C++17	38 / 100	5079 ms	57548 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];
            }
            for (auto k : pos) {
                nxt[k] = j;
                tM.upd(k, 2e18);
            }
            if (was != j) {
                nxt[was] = j;
            }
            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) {
            ans[i] = max(0ll, x + val);
        } else {
            ans[i] = min(x, val);
        }
    }

    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
88 49 94 26 31 20 35 61 24 33
10
0 9 79
0 9 83
0 9 26
0 9 11
0 9 63
0 9 13
0 9 9
0 9 94
0 9 50
0 9 84
88 49 94 26 31 20 35 61 24 33

10
94 64 84 2 39 19 82 24 28 0

10
0 9 19
0 9 90
0 9 80
0 9 5
0 9 31
0 9 95
0 9 53
0 9 20
0 9 84
0 9 31
94 64 84 2 39 19 82 24 28 0

*/

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