Submission #1071795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071795		shmax	Distributing Candies (IOI21_candies)	C++17	29 / 100	775 ms	25172 KiB

candies

#include <bits/stdc++.h>

using namespace std;
using i32 = int;
#define int long long
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
template<typename T>
using vec = vector<T>;

const int maxN = 2e5 + 5;

struct Push {
    int to_add;
    bool set_0;
    bool set_mx;
};

Push combine_push(const optional<Push> &att, const Push &b) {
    if (b.set_0)
        return b;
    if (b.set_mx)
        return b;
    if (!att.has_value())
        return b;
    auto a = *att;
    if (a.set_0) {
        return {a.to_add + b.to_add, true, false};
    }
    if (a.set_mx) {
        return {a.to_add + b.to_add, false, true};
    }
    return {a.to_add + b.to_add, false, false};
}

vec<i32> tc;
int stree[maxN];
optional<Push> pushes[4 * maxN + 5];

void build() {
    memset(stree, 0, sizeof stree);
    for (int i = 0; i < 4 * maxN + 5; i++)pushes[i] = nullopt;
}

void push(int v, int tl, int tr) {
    if (!pushes[v].has_value()) return;
    if (tl != tr) {
        pushes[2 * v] = combine_push(pushes[2 * v], *pushes[v]);
        pushes[2 * v + 1] = combine_push(pushes[2 * v + 1], *pushes[v]);
        int tm = (tl + tr) / 2;
        if (tl == tm) {
            if (pushes[2 * v].has_value()) {
                if (pushes[2 * v]->set_0) {
                    stree[tl] = 0;
                    stree[tl] += pushes[2 * v]->to_add;
                } else if (pushes[2 * v]->set_mx) {
                    stree[tl] = tc[tl];
                    stree[tl] += pushes[2 * v]->to_add;
                } else {
                    stree[tl] += pushes[v]->to_add;
                }
            }
        }
        if (tm + 1 == tr) {
            if (pushes[2 * v + 1].has_value()) {
                if (pushes[2 * v + 1]->set_0) {
                    stree[tr] = 0;
                    stree[tr] += pushes[2 * v + 1]->to_add;
                } else if (pushes[2 * v + 1]->set_mx) {
                    stree[tr] = tc[tr];
                    stree[tr] += pushes[2 * v + 1]->to_add;
                } else {
                    stree[tr] += pushes[v]->to_add;
                }
            }
        }
    }
    pushes[v] = nullopt;
}

int get(int v, int tl, int tr, int pos) {
    push(v, tl, tr);
    if (tl == tr) {
        return stree[tl];
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return get(v * 2, tl, tm, pos);
    else
        return get(v * 2 + 1, tm + 1, tr, pos);
}


void update(int v, int tl, int tr, int l, int r, Push p) {
    push(v, tl, tr);
    if (tl == l and tr == r) {
        pushes[v] = p;
        if (l == r) {
            if (pushes[v].has_value()) {
                if (pushes[v]->set_0) {
                    stree[tl] = 0;
                } else if (pushes[v]->set_mx) {
                    stree[tl] = tc[tl];
                }
                stree[tr] += pushes[v]->to_add;
            }
        }
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    if (r <= tm)
        update(v * 2, tl, tm, l, r, p);
    else if (l > tm)
        update(v * 2 + 1, tm + 1, tr, l, r, p);
    else
        update(v * 2, tl, tm, l, tm, p), update(v * 2 + 1, tm + 1, tr, tm + 1, r, p);
}

vec<i32> distribute_candies(vec<i32> C, vec<i32> L, vec<i32> R, vec<i32> V) {
    int n = len(C);
    vec<pair<int, int>> rc(n);
    for (int i = 0; i < n; i++) {
        rc[i] = {C[i], i};
    }
    sort(all(rc));
    sort(all(C));

    tc = C;
    build();
    for (int i = 0; i < len(L); i++) {
        int v = V[i];
        if (v == 0)continue;
        if (v > 0) {
            if (get(1, 0, n - 1, 0) + v <= C[0]) {
                update(1, 0, n - 1, 0, n - 1, Push{v, false, false});
            } else {
                int tl = 0;
                int tr = n - 1;
                while (tl != tr) {
                    int tm = (tl + tr + 1) / 2;
                    if ((get(1, 0, n - 1, tm) + v > C[tm])) {
                        tl = tm;
                    } else {
                        tr = tm - 1;
                    }
                }
                update(1, 0, n - 1, 0, tl, Push{0, false, true});
                if (tl != n - 1) {
                    update(1, 0, n - 1, tl + 1, n - 1, Push{v, false, false});
                }
            }
        } else {
            if (get(1, 0, n - 1, 0) + v >= 0) {
                update(1, 0, n - 1, 0, n - 1, Push{v, false, false});
            } else {
                int tl = 0;
                int tr = n - 1;
                while (tl != tr) {
                    int tm = (tl + tr + 1) / 2;
                    if (get(1, 0, n - 1, tm) + v < 0) {
                        tl = tm;
                    } else {
                        tr = tm - 1;
                    }
                }
                update(1, 0, n - 1, 0, tl, Push{0, true, false});
                if (tl != n - 1) {
                    update(1, 0, n - 1, tl + 1, n - 1, Push{v, false, false});
                }
            }
        }
    }
    vec<i32> ans(n);
    for (int i = 0; i < n; i++) {
        ans[rc[i].second] = get(1, 0, n - 1, i);
    }
    return ans;
}

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