oj.uz

Submission #435171

# Submission time Handle Problem Language Result Execution time Memory
435171 2021-06-23T04:47:36 Z ecnerwala Distributing Candies (IOI21_candies) C++17
100 / 100
 516 ms 34156 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 34156 KB Output is correct
2 Correct 447 ms 34028 KB Output is correct
3 Correct 456 ms 34040 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 206 ms 23752 KB Output is correct
3 Correct 78 ms 7596 KB Output is correct
4 Correct 405 ms 34012 KB Output is correct
5 Correct 488 ms 33972 KB Output is correct
6 Correct 474 ms 34156 KB Output is correct
7 Correct 401 ms 34124 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 105 ms 23172 KB Output is correct
4 Correct 85 ms 7532 KB Output is correct
5 Correct 184 ms 30152 KB Output is correct
6 Correct 212 ms 30236 KB Output is correct
7 Correct 190 ms 30256 KB Output is correct
8 Correct 175 ms 30196 KB Output is correct
9 Correct 223 ms 30192 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 442 ms 34156 KB Output is correct
7 Correct 447 ms 34028 KB Output is correct
8 Correct 456 ms 34040 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 206 ms 23752 KB Output is correct
11 Correct 78 ms 7596 KB Output is correct
12 Correct 405 ms 34012 KB Output is correct
13 Correct 488 ms 33972 KB Output is correct
14 Correct 474 ms 34156 KB Output is correct
15 Correct 401 ms 34124 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 105 ms 23172 KB Output is correct
19 Correct 85 ms 7532 KB Output is correct
20 Correct 184 ms 30152 KB Output is correct
21 Correct 212 ms 30236 KB Output is correct
22 Correct 190 ms 30256 KB Output is correct
23 Correct 175 ms 30196 KB Output is correct
24 Correct 223 ms 30192 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 97 ms 7604 KB Output is correct
27 Correct 218 ms 23644 KB Output is correct
28 Correct 474 ms 34012 KB Output is correct
29 Correct 495 ms 34092 KB Output is correct
30 Correct 498 ms 34016 KB Output is correct
31 Correct 434 ms 34116 KB Output is correct
32 Correct 516 ms 34048 KB Output is correct