Submission #435171

#	Time	Username	Problem	Language	Result	Execution time	Memory
435171		ecnerwala	Distributing Candies (IOI21_candies)	C++17	100 / 100	516 ms	34156 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

std::vector<int> distribute_candies(
    std::vector<int> C,
    std::vector<int> L,
    std::vector<int> R,
    std::vector<int> V
) {
    struct range_data {
        int64_t pref_min, pref_max, tot_val;
        bool incr;

        explicit range_data(int v = 0) {
            pref_min = std::min(0, v);
            pref_max = std::max(0, v);
            tot_val = v;
            incr = (v >= 0);
        }
        range_data(range_data a, range_data b) {
            pref_min = std::min(a.pref_min, a.tot_val + b.pref_min);
            pref_max = std::max(a.pref_max, a.tot_val + b.pref_max);
            tot_val = a.tot_val + b.tot_val;
            incr = a.incr;
        }

        int64_t range() const {
            return pref_max - pref_min;
        }
    };

    int N = int(C.size());
    int Q = int(L.size());
    assert(Q == int(R.size()));
    assert(Q == int(V.size()));
    int S = 1; while (S < Q+1) S *= 2;

    std::vector<range_data> seg(2*S);
    auto update_node = [&](int a) -> void {
        seg[a] = range_data(seg[2*a], seg[2*a+1]);
    };
    auto update_parents = [&](int a) -> void {
        for (a >>= 1; a; a >>= 1) update_node(a);
    };
    seg[S] = range_data(-*max_element(C.begin(), C.end()));
    update_parents(S);

    std::vector<std::vector<int>> evts(N+1);
    for (int q = 0; q < Q; q++) {
        evts[L[q]].push_back(q);
        evts[R[q]+1].push_back(~q);
    }

    std::vector<int> ans(N);
    for (int i = 0; i < N; i++) {
        for (int q : evts[i]) {
            if (q < 0) {
                q = ~q;
                seg[S+1+q] = range_data();
            } else {
                seg[S+1+q] = range_data(V[q]);
            }
            update_parents(S+1+q);
        }

        range_data cur_suff;
        int a = 1;
        while (a < S) {
            assert(cur_suff.range() < C[i]);
            assert(range_data(seg[a], cur_suff).range() >= C[i]);
            a <<= 1;
            a ++;
            range_data rhs = range_data(seg[a], cur_suff);
            if (rhs.range() >= C[i]) {
                // Keep digging
            } else {
                cur_suff = rhs;
                a--;
            }
        }
        assert(cur_suff.range() < C[i]);
        cur_suff = range_data(seg[a], cur_suff);
        assert(cur_suff.range() >= C[i]);
        ans[i] = cur_suff.incr ? int(C[i] - (cur_suff.pref_max - cur_suff.tot_val)) : int(cur_suff.tot_val - cur_suff.pref_min);
    }

    return ans;
}

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