Submission #1256222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256222		biank	Distributing Candies (IOI21_candies)	C++20	100 / 100	717 ms	36172 KiB

candies

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define dforn(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using vi = vector<int>;
using vb = vector<bool>;
using ii = pair<int, int>;
using ll = long long;

#define pb push_back
#define eb emplace_back

const int SZ = 1 << 18;
const ll INF = 1e18;

pair<ll, ll> st[2 * SZ];
ll lazy[2 * SZ];
int C;
 
#define fst first
#define snd second
 
void pass(int u) {
    if (u < SZ) {
        lazy[2 * u] += lazy[u];
        lazy[2 * u + 1] += lazy[u];
    }
    st[u].fst += lazy[u];
    st[u].snd += lazy[u];
    lazy[u] = 0;
}
 
void update(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
    pass(u);
    if (e <= l || r <= s) return;
    if (s <= l && r <= e) {
        lazy[u] = v;
        return pass(u);
    }
    int m = (l + r) / 2;
    update(s, e, v, l, m, 2 * u);
    update(s, e, v, m, r, 2 * u + 1);
    st[u].fst = min(st[2 * u].fst, st[2 * u + 1].fst);
    st[u].snd = max(st[2 * u].snd, st[2 * u + 1].snd);
} 

ll queryMin(int s, int e, int l = 0, int r = SZ, int u = 1) {
    pass(u);
    if (e <= l || r <= s) return INF;
    if (s <= l && r <= e) return st[u].fst;
    int m = (l + r) / 2;
    return min(queryMin(s, e, l, m, 2 * u), queryMin(s, e, m, r, 2 * u + 1));
}

ll queryMax(int s, int e, int l = 0, int r = SZ, int u = 1) {
    pass(u);
    if (e <= l || r <= s) return -INF;
    if (s <= l && r <= e) return st[u].snd;
    int m = (l + r) / 2;
    return max(queryMax(s, e, l, m, 2 * u), queryMax(s, e, m, r, 2 * u + 1));
}

ll get(int p) { return queryMax(p, p + 1); }

int find(int c, int u, ll mini, ll maxi) {
    while (u < SZ) {
        u = 2 * u + 1;
        pass(u);
        if (max(st[u].snd, maxi) - min(st[u].fst, mini) < c) {
            maxi = max(maxi, st[u].snd);
            mini = min(mini, st[u].fst);
            u--;
            pass(u);
        }
    }
    return u - SZ;
}

int find(int l, int r, int c) {
    vi left, right;
    for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
        if (l & 1) left.pb(l++);
        if (r & 1) right.pb(--r);
    }
    ll mini = INF, maxi = -INF;
    vi nodes = right;
    dforn(i, sz(left)) nodes.pb(left[i]);
    for (int u : nodes) {
        pass(u);
        if (max(st[u].snd, maxi) - min(st[u].fst, mini) >= c) {
            return find(c, u, mini, maxi);
        }
        maxi = max(maxi, st[u].snd);
        mini = min(mini, st[u].fst);
    }
    return -1;
}

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = sz(c), q = sz(v);
    vector<vector<ii>> add(n + 1), sub(n + 1);
    forn(i, 2 * SZ) st[i].fst = INF, st[i].snd = -INF;
    forsn(i, SZ, SZ + q + 1) st[i].fst = st[i].snd = 0;
    dforsn(i, 1, SZ) {
        st[i].fst = min(st[2 * i].fst, st[2 * i + 1].fst);
        st[i].snd = max(st[2 * i].snd, st[2 * i + 1].snd);
    }
    forn(i, q) {
        add[l[i]].eb(i, v[i]);
        sub[r[i] + 1].eb(i, v[i]);
    }
    vi ret(n);
    forn(i, n) {
        for (auto [j, x] : add[i]) update(j + 1, q + 1, x);
        for (auto [j, x] : sub[i]) update(j + 1, q + 1, -x);
        int lo = find(0, q + 1, c[i]);
        ll tot = get(q);
        if (lo == -1) {
            ret[i] = tot - queryMin(0, q + 1);
        } else if (tot - get(lo) > 0) {
            ll diff = tot - queryMax(lo, q + 1);
            ret[i] = c[i] + diff;
        } else { 
            ll diff = tot - queryMin(lo, q + 1);
            ret[i] = diff;
        }
    }
    return ret;
}

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