| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 815578 | t6twotwo | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> mn, mn2, mx, mx2, lazy;
void apply_add(int p, ll v) {
lazy[p] += v;
mn[p] += v;
mx[p] += v;
if (mn2[p] != inf) {
mn2[p] += v;
}
if (mx2[p] != -inf) {
mx2[p] += v;
}
}
void apply_upd(int p, ll cmn, ll cmx) {
if (cmn == cmx) {
mn[p] = mx[p] = cmn;
mn2[p] = inf;
mx2[p] = -inf;
} else {
if (cmn < mx[p]) {
if (mn[p] == mx[p]) {
mn[p] = cmn;
}
if (mn2[p] == mx[p]) {
mn2[p] = cmn;
}
mx[p] = cmn;
}
if (cmx > mn[p]) {
if (mx[p] == mn[p]) {
mx[p] = cmx;
}
if (mx2[p] == mn[p]) {
mx2[p] = cmx;
}
mn[p] = cmx;
}
}
}
void push_add(int p) {
apply_add(p * 2, lazy[p]);
apply_add(p * 2 + 1, lazy[p]);
lazy[p] = 0;
}
void push_upd(int p) {
apply_upd(p * 2, mx[p], mn[p]);
apply_upd(p * 2 + 1, mx[p], mn[p]);
}
void pull(int p) {
int l = p * 2;
int r = p * 2 + 1;
mx[p] = max(mx[l], mx[r]);
mn[p] = min(mn[l], mn[r]);
mx2[p] = max(mx[p] == mx[l] ? mx2[l] : mx[l], mx[p] == mx[r] ? mx2[r] : mx[r]);
mn2[p] = min(mn[p] == mn[l] ? mn2[l] : mn[l], mn[p] == mn[r] ? mn2[r] : mn[r]);
}
void add(int p, int l, int r, int L, int R, int v) {
if (R <= l || r <= L) {
return;
}
if (L <= l && r <= R) {
apply_add(p, v);
return;
}
int m = (l + r + 1) / 2;
push_add(p);
push_upd(p);
add(p * 2, l, m, L, R, v);
add(p * 2 + 1, m, r, L, R, v);
pull(p);
}
void upd(int p, int l, int r, int L, int R, ll v, bool f) {
if (R <= l || r <= L || (!f && v >= mx[p]) || (f && v <= mn[p])) {
return;
}
if (L <= l && r <= R && (mn[p] == mx[p] || (!f && v > mx2[p]) || (f && v < mn2[p]))) {
if (f) {
apply_upd(p, inf, v);
} else {
apply_upd(p, v, -inf);
}
return;
}
int m = (l + r + 1) / 2;
push_add(p);
push_upd(p);
upd(p * 2, l, m, L, R, v, f);
upd(p * 2 + 1, m, r, L, R, v, f);
pull(p);
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
for (int &x : R) {
x++;
}
int N = C.size(), Q = V.size();
if (N <= 2000 && Q <= 2000) {
vector<int> A(N);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j < R[i]; j++) {
A[j] += V[i];
A[j] = max(A[j], 0);
A[j] = min(A[j], C[j]);
}
}
return A;
}
if (*min_element(V.begin(), V.end()) > 0) {
vector<ll> s(N + 1);
for (int i = 0; i < Q; i++) {
s[L[i]] += V[i];
s[R[i]] -= V[i];
}
vector<int> A(N);
for (int i = 0; i < N; i++) {
A[i] = min((ll)C[i], s[i]);
s[i + 1] += s[i];
}
return A;
}
int M = 2 << __lg(N - 1);
if (L == vector(Q, 0) && R == vector(Q, N)) {
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return C[i] < C[j];
});
vector<int> st(2 * M), df(2 * M);
auto pull = [&](int i) {
st[i] = max(st[i * 2], st[i * 2 + 1]);
df[i] = max(df[i * 2], df[i * 2 + 1]);
};
auto upd = [&](auto upd, int p, int l, int r, int L, int R, int f, int v) -> void {
if (R <= l || r <= L) {
return;
}
if (l + 1 == r) {
assert(p - M == l);
if (f == 0) {
st[p] = 0;
df[p] = C[ord[l]];
} else if (f == 1) {
st[p] = C[ord[l]];
df[p] = 0;
} else {
st[p] += v;
df[p] -= v;
}
return;
}
int m = (l + r + 1) / 2;
upd(upd, p * 2, l, m, L, R, f, v);
upd(upd, p * 2 + 1, m, r, L, R, f, v);
pull(p);
};
auto find = [&](auto find, int p, int l, int r, int v, vector<int> &s) -> int {
if (l + 1 == r) {
return l;
}
int m = (l + r + 1) / 2;
if (s[p * 2] >= v) {
return find(find, p * 2, l, m, v, s);
} else {
return find(find, p * 2 + 1, m, r, v, s);
}
};
for (int i = 0; i < N; i++) {
df[i + M] = C[ord[i]];
}
for (int i = M - 1; i; i--) {
pull(i);
}
for (int i = 0; i < Q; i++) {
if (V[i] < 0) {
int f = st[1] < -V[i] ? N : find(find, 1, 0, M, -V[i], st);
upd(upd, 1, 0, M, 0, f, 0, 0);
upd(upd, 1, 0, M, f, N, 2, V[i]);
} else {
int f = df[1] < V[i] ? N : find(find, 1, 0, M, V[i], df);
upd(upd, 1, 0, M, 0, f, 1, 0);
upd(upd, 1, 0, M, f, N, 2, V[i]);
}
}
auto qry = [&](auto qry, int p, int l, int r) -> void {
if (l + 1 >= r) {
return;
}
int m = (l + r + 1) / 2;
push(p, l, r);
qry(qry, p * 2, l, m);
qry(qry, p * 2 + 1, m, r);
};
qry(qry, 1, 0, M);
vector<int> ans(N);
for (int i = 0; i < N; i++) {
ans[ord[i]] = st[i + M];
}
return ans;
}
mn.resize(2 * M, 0);
mx.resize(2 * M, 0);
mn2.resize(2 * M, inf);
mx2.resize(2 * M, -inf);
lazy.resize(2 * M);
for (int i = 0; i < Q; i++) {
add(1, 0, M, L[i], R[i], V[i]);
if (V[i] > 0) {
upd(1, 0, M, L[i], R[i], C[0], 0);
} else {
upd(1, 0, M, L[i], R[i], 0, 1);
}
}
for (int i = 1; i < M; i++) {
push_add(i);
push_upd(i);
}
vector<int> ans(N);
for (int i = 0; i < N; i++) {
ans[i] = mx[i + M];
}
return ans;
}