| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1241962 | hayford08 | Distributing Candies (IOI21_candies) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
struct SegBeats {
struct Node {
int mx, sx, cnt_mx;
int mn, sn, cnt_mn;
long long sum;
long long add;
};
int n;
vector<Node> st;
SegBeats(int _n): n(_n), st(4*n) {
build(1, 0, n-1);
}
void build(int p, int L, int R) {
auto &nd = st[p];
nd.add = 0;
nd.sum = 0;
nd.mx = nd.mn = 0;
nd.sx = -INF; nd.sn = INF;
nd.cnt_mx = nd.cnt_mn = R-L+1;
if (L==R) return;
int M=(L+R)/2;
build(p<<1, L, M);
build(p<<1|1, M+1, R);
}
// push down lazy tags and chmin/chmax constraints
void push(int p, int L, int R) {
// apply pending add
if (st[p].add) apply_add(p<<1, st[p].add);
if (st[p].add) apply_add(p<<1|1, st[p].add);
st[p].add = 0;
// push down a chmin if current mx < child mx
push_chmin(p<<1, st[p].mx);
push_chmin(p<<1|1, st[p].mx);
// push down a chmax if current mn > child mn
push_chmax(p<<1, st[p].mn);
push_chmax(p<<1|1, st[p].mn);
}
// apply range_add to node p
void apply_add(int p, long long v) {
auto &nd = st[p];
nd.mx += v; nd.mn += v;
if (nd.sx != -INF) nd.sx += v;
if (nd.sn != INF) nd.sn += v;
nd.sum += v * (nd.cnt_mx + (nd.sum - nd.mx * nd.cnt_mx) / (nd.mn));
nd.add += v;
}
// apply chmin(x) to node p if needed
void push_chmin(int p, int x) {
auto &nd = st[p];
if (nd.mx <= x) return;
nd.sum -= 1LL*(nd.mx - x)*nd.cnt_mx;
nd.mx = x;
// if the new mx equals the second max, we may need to adjust sx/cnt
if (nd.mx == nd.sx) {
nd.sx = -INF;
nd.cnt_mx += /*cnt of old sx*/;
}
// same logic for minima side if needed...
}
// apply chmax(x) similarly
void push_chmax(int p, int x) { /* mirror of chmin */ }
// pull up from children
void pull(int p) {
auto &nd = st[p];
auto &L = st[p<<1], &R = st[p<<1|1];
// update sum
nd.sum = L.sum + R.sum;
// update mx, cnt_mx, sx
if (L.mx > R.mx) {
nd.mx = L.mx; nd.cnt_mx = L.cnt_mx;
nd.sx = max(L.sx, R.mx);
} else if (R.mx > L.mx) {
nd.mx = R.mx; nd.cnt_mx = R.cnt_mx;
nd.sx = max(R.sx, L.mx);
} else { // equal
nd.mx = L.mx;
nd.cnt_mx = L.cnt_mx + R.cnt_mx;
nd.sx = max(L.sx, R.sx);
}
// update mn, cnt_mn, sn similarly...
}
// range add
void range_add(int i, int j, int v) { upd_add(1,0,n-1,i,j,v); }
void upd_add(int p, int L, int R, int i, int j, int v) {
if (j< L || R< i) return;
if (i <= L && R <= j) { apply_add(p, v); return; }
push(p, L, R);
int M=(L+R)/2;
upd_add(p<<1, L, M, i, j, v);
upd_add(p<<1|1, M+1, R, i, j, v);
pull(p);
}
// range chmin
void range_chmin(int i, int j, int x) { upd_chmin(1,0,n-1,i,j,x); }
void upd_chmin(int p, int L, int R, int i, int j, int x) {
if (j< L || R< i || st[p].mx <= x) return;
if (i <= L && R <= j && st[p].sx < x) {
push_chmin(p, x);
return;
}
push(p, L, R);
int M=(L+R)/2;
upd_chmin(p<<1, L, M, i, j, x);
upd_chmin(p<<1|1, M+1, R, i, j, x);
pull(p);
}
// range chmax (mirror)
void range_chmax(int i, int j, int x) { /* … */ }
// finally, collect all leaves
void collect(int p, int L, int R, vector<int>& out) {
if (L==R) {
out[L] = st[p].mx; // == st[p].mn == final value
return;
}
push(p, L, R);
int M=(L+R)/2;
collect(p<<1, L, M, out);
collect(p<<1|1, M+1, R, out);
}
};
// Usage:
vector<int> distribute_candies(
const vector<int>& c,
const vector<int>& l,
const vector<int>& r,
const vector<int>& v
) {
int n = c.size(), q = l.size();
int C = c[0]; // all capacities are the same
SegBeats seg(n);
for (int j = 0; j < q; j++) {
if (v[j] > 0) {
seg.range_add(l[j], r[j], v[j]);
seg.range_chmin(l[j], r[j], C);
} else {
seg.range_add(l[j], r[j], v[j]);
seg.range_chmax(l[j], r[j], 0);
}
}
vector<int> ans(n);
seg.collect(1, 0, n-1, ans);
return ans;
}