Submission #507676

#	Time	Username	Problem	Language	Result	Execution time	Memory
507676		ITO	Distributing Candies (IOI21_candies)	C++17	100 / 100	533 ms	23500 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
int n, smax[800001], smin[800001], scur[800001], scap[800001], cc[200001], inf = 2000000001;
vector<int> s;
int mincap(int id, int l, int r, int ll, int rr) {
    if (l > rr || r < ll) return l;
    if (l <= ll && r >= rr) return scap[id];
    int mid = (ll + rr) / 2, x1 = mincap(id * 2, l, r, ll, mid), x2 = mincap(id * 2 + 1, l, r, mid + 1, rr);
    if (cc[x1] < cc[x2]) return x1;
    return x2;
}
void updcap(int id, int lr, int ll, int rr) {
    if (ll == rr) {
        scap[id] = lr;
        return;
    }
    int mid = (ll + rr) / 2;
    if (lr <= mid) {
        updcap(id * 2, lr, ll, mid);
    } else {
        updcap(id * 2 + 1, lr, mid + 1, rr);
    }
    if (cc[scap[id * 2]] < cc[scap[id * 2 + 1]]) {
        scap[id] = scap[id * 2];
    } else {
        scap[id] = scap[id * 2 + 1];
    }
    return;
}
pair<int, pair<int, int>> eat(int id, int lr, int ll, int rr) {
    pair<int, pair<int, int>> px;
    if (ll == rr) {
        px = make_pair(scur[id], make_pair(smax[id], smin[id]));
        return px;
    }
    int mid = (ll + rr) / 2;
    if (lr <= mid) {
        px = eat(id * 2, lr, ll, mid);
    } else {
        px = eat(id * 2 + 1, lr, mid + 1, rr);
    }
    if (px.first == inf) return px;
    int dif = max(smax[id] + px.first, px.second.first) - min(smin[id] + px.first, px.second.second);
    if (dif >= cc[lr]) {
        if (smax[id] + px.first > px.second.first) {
            s[lr] = - px.second.second;
        } else {
            s[lr] = cc[lr] - px.second.first;
        }
        cc[lr] = inf;
        updcap(1, lr, 0, n - 1);
        px.first = inf;
    } else {
        px.second.first = max(smax[id] + px.first, px.second.first);
        px.second.second = min(smin[id] + px.first, px.second.second);
        px.first += scur[id];
    }
    return px;
}
void puttag(int id, int ma, int mi, int cu) {
    if (cc[scap[id]] == inf) return;
    int dif = max(ma + scur[id], smax[id]) - min(mi + scur[id], smin[id]);
    while (dif >= cc[scap[id]]) {
        pair<int, pair<int, int>> px = eat(1, scap[id], 0, n - 1);
        if (px.first != inf) {
            if (ma + px.first > px.second.first) {
                s[scap[id]] = - px.second.second;
            } else {
                s[scap[id]] = cc[scap[id]] - px.second.first;
            }
            cc[scap[id]] = inf;
            updcap(1, scap[id], 0, n - 1);
            px.first = inf;
        }
    }
    smax[id] = max(ma + scur[id], smax[id]);
    smin[id] = min(mi + scur[id], smin[id]);
    scur[id] += cu;
    return;
}
void push(int id) {
    int ma = smax[id], mi = smin[id], cu = scur[id];
    smax[id] = 0, smin[id] = 0, scur[id] = 0;
    puttag(id * 2, ma, mi, cu);
    puttag(id * 2 + 1, ma, mi, cu);
    return;
}
void modify(int id, int val, int l, int r, int ll, int rr) {
    if (l > rr || r < ll) return;
    if (l <= ll && r >= rr) {
        puttag(id, max(0, -val), min(0, -val), -val);
        return;
    }
    push(id);
    int mid = (ll + rr) / 2;
    modify(id * 2, val, l, r, ll, mid);
    modify(id * 2 + 1, val, l, r, mid + 1, rr);
    return;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = c.size();
    s.resize(n);
    for (int i = 0; i < n; i++) {
        cc[i] = c[i];
        updcap(1, i, 0, n - 1);
    }
    for (int i = l.size() - 1; i >= 0; i--) {
        modify(1, v[i], l[i], r[i], 0, n - 1);
    }
    for (int i = 0; i < n; i++) {
        if (cc[i] != inf) {
            pair<int, pair<int, int>> px = eat(1, i, 0, n - 1);
            if (px.first != inf) {
                s[i] = - px.second.second;
            }
        }
    }
    return s;
}

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