Submission #626652

#	Time	Username	Problem	Language	Result	Execution time	Memory
626652		tabr	Distributing Candies (IOI21_candies)	C++17	100 / 100	1311 ms	33440 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

// editorial

struct segtree {
    using T = pair<long long, long long>;
    using F = long long;

    T e() {
        return make_pair((long long) 1e18, (long long) -1e18);
    }

    F id() {
        return 0;
    }

    T op(T a, T b) {
        a.first = min(a.first, b.first);
        a.second = max(a.second, b.second);
        return a;
    }

    T mapping(F f, T x) {
        x.first += f;
        x.second += f;
        return x;
    }

    F composition(F f, F g) {
        return f + g;
    }

    int n;
    int size;
    int log_size;
    vector<T> node;
    vector<F> lazy;

    segtree() : segtree(0) {}
    segtree(int _n) {
        build(vector<T>(_n, e()));
    }
    segtree(const vector<T>& v) {
        build(v);
    }

    void build(const vector<T>& v) {
        n = (int) v.size();
        if (n <= 1) {
            log_size = 0;
        } else {
            log_size = 32 - __builtin_clz(n - 1);
        }
        size = 1 << log_size;
        node.resize(2 * size, e());
        lazy.resize(size, id());
        for (int i = 0; i < n; i++) {
            node[i + size] = v[i];
        }
        for (int i = size - 1; i > 0; i--) {
            pull(i);
        }
    }

    void push(int x) {
        node[2 * x] = mapping(lazy[x], node[2 * x]);
        node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]);
        if (2 * x < size) {
            lazy[2 * x] = composition(lazy[x], lazy[2 * x]);
            lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]);
        }
        lazy[x] = id();
    }

    void pull(int x) {
        node[x] = op(node[2 * x], node[2 * x + 1]);
    }

    void set(int p, T v) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        node[p] = v;
        for (int i = 1; i <= log_size; i++) {
            pull(p >> i);
        }
    }

    T get(int p) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        return node[p];
    }

    T get(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        for (int i = log_size; i >= 1; i--) {
            if (((l >> i) << i) != l) {
                push(l >> i);
            }
            if (((r >> i) << i) != r) {
                push((r - 1) >> i);
            }
        }
        T vl = e();
        T vr = e();
        while (l < r) {
            if (l & 1) {
                vl = op(vl, node[l++]);
            }
            if (r & 1) {
                vr = op(node[--r], vr);
            }
            l >>= 1;
            r >>= 1;
        }
        return op(vl, vr);
    }

    void apply(int p, F f) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        node[p] = mapping(f, node[p]);
        for (int i = 1; i <= log_size; i++) {
            pull(p >> i);
        }
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        for (int i = log_size; i >= 1; i--) {
            if (((l >> i) << i) != l) {
                push(l >> i);
            }
            if (((r >> i) << i) != r) {
                push((r - 1) >> i);
            }
        }
        int ll = l;
        int rr = r;
        while (l < r) {
            if (l & 1) {
                node[l] = mapping(f, node[l]);
                if (l < size) {
                    lazy[l] = composition(f, lazy[l]);
                }
                l++;
            }
            if (r & 1) {
                r--;
                node[r] = mapping(f, node[r]);
                if (l < size) {
                    lazy[r] = composition(f, lazy[r]);
                }
            }
            l >>= 1;
            r >>= 1;
        }
        l = ll;
        r = rr;
        for (int i = 1; i <= log_size; i++) {
            if (((l >> i) << i) != l) {
                pull(l >> i);
            }
            if (((r >> i) << i) != r) {
                pull((r - 1) >> i);
            }
        }
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int) c.size();
    int q = (int) v.size();
    segtree seg(vector<pair<long long, long long>>(q + 1, make_pair(0LL, 0LL)));
    vector<vector<int>> events(n + 1);
    for (int i = 0; i < q; i++) {
        events[l[i]].emplace_back(i);
        events[r[i] + 1].emplace_back(i);
    }
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        for (int j : events[i]) {
            if (l[j] == i) {
                seg.apply(j + 1, q + 1, v[j]);
            } else {
                seg.apply(j + 1, q + 1, -v[j]);
            }
        }
        auto last = seg.get(q).first;
        int low = -1;
        int high = q;
        while (high - low > 1) {
            int mid = (high + low) >> 1;
            auto p = seg.get(mid, q);
            if (p.second - p.first <= c[i]) {
                high = mid;
            } else {
                low = mid;
            }
        }
        debug(low, seg.node[1]);
        if (low == -1) {
            res[i] = (int) (last - seg.node[1].first);
        } else {
            auto p = seg.get(low, q);
            auto now = seg.get(low).first;
            if (p.second == now) {
                res[i] = (int) (last - p.first);
            } else if (p.first == now) {
                res[i] = (int) (c[i] + last - p.second);
            } else {
                assert(false);
            }
        }
        res[i] = min(c[i], max(0, res[i]));
    }
    return res;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    debug(distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11}));
    debug(distribute_candies({10}, {0, 0}, {0, 0}, {-3, 12}));
    return 0;
}
#endif

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