Submission #1243031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243031		nibert	Distributing Candies (IOI21_candies)	C++20	0 / 100	156 ms	14508 KiB

candies

#include <vector>
#include <algorithm>
using namespace std;

struct SegmentTree {
    int n;
    vector<int> tree, lazy, cap;

    SegmentTree(const vector<int>& capacity) {
        n = capacity.size();
        cap = capacity;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }

    void push(int node, int l, int r) {
        if (lazy[node] == 0) return;
        if (l == r) {
            tree[node] = min(cap[l], tree[node] + lazy[node]);
        } else {
            int mid = (l + r) / 2;
            // propagate lazily to children
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int node, int l, int r, int ql, int qr, int val) {
        push(node, l, r);
        if (r < ql || l > qr) return;

        if (ql <= l && r <= qr) {
            lazy[node] += val;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(2*node, l, mid, ql, qr, val);
        update(2*node+1, mid+1, r, ql, qr, val);
        tree[node] = 0; // not needed unless we do queries
    }

    void get_final(int node, int l, int r, vector<int>& result) {
        push(node, l, r);
        if (l == r) {
            result[l] = tree[node];
            return;
        }
        int mid = (l + r) / 2;
        get_final(2*node, l, mid, result);
        get_final(2*node+1, mid+1, r, result);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    SegmentTree seg(c);

    for (int i = 0; i < q; ++i) {
        seg.update(1, 0, n - 1, l[i], r[i], v[i]);
    }

    vector<int> result(n);
    seg.get_final(1, 0, n - 1, result);
    return result;
}

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