Submission #1243309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243309		nibert	Distributing Candies (IOI21_candies)	C++20	3 / 100	5094 ms	9288 KiB

candies

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

const int MAXN = 1 << 18;

int t[MAXN * 4];  // segment tree
int c[MAXN];      // max capacity per box

// Build just to initialize segment tree
void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = 0;
    } else {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        t[v] = 0;
    }
}

// Update range [l, r] with +add, while clamping after each update
void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r || tr < l || tl > r) return;
    if (tl == tr) {
        t[v] = clamp(t[v] + add, 0, c[tl]);
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, r, add);
        update(v*2+1, tm+1, tr, l, r, add);
        // No need to maintain sums because we only care about point values
    }
}

// Query final value at position pos
int query(int v, int tl, int tr, int pos) {
    if (tl == tr) return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm) return query(v*2, tl, tm, pos);
    else return query(v*2+1, tm+1, tr, pos);
}

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

    // Copy capacities
    for (int i = 0; i < n; ++i) c[i] = capacity[i];

    // Build segment tree
    build(1, 0, n - 1);

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

    // Get final values
    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        res[i] = query(1, 0, n - 1, i);
    }

    return res;
}

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