#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> A(N);
for (int i = 0; i < Q; i++) {
if (V[i] > 0) {
int p = 0;
while (p < N && A[ord[p]] + V[i] >= C[ord[p]]) {
p++;
}
for (int j = 0; j < p; j++) {
A[ord[j]] = C[ord[j]];
}
for (int j = p; j < N; j++) {
A[ord[j]] += V[i];
}
} else {
int p = 0;
while (p < N && A[ord[p]] + V[i] <= 0) {
p++;
}
for (int j = 0; j < p; j++) {
A[ord[j]] = 0;
}
for (int j = p; j < N; j++) {
A[ord[j]] += V[i];
}
}
}
return A;
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
8808 KB |
Output is correct |
| 2 |
Correct |
76 ms |
8820 KB |
Output is correct |
| 3 |
Correct |
76 ms |
8800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
154 ms |
5784 KB |
Output is correct |
| 3 |
Correct |
61 ms |
24356 KB |
Output is correct |
| 4 |
Correct |
436 ms |
27816 KB |
Output is correct |
| 5 |
Correct |
499 ms |
27960 KB |
Output is correct |
| 6 |
Correct |
767 ms |
27880 KB |
Output is correct |
| 7 |
Correct |
678 ms |
27880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
370 ms |
6508 KB |
Output is correct |
| 4 |
Correct |
839 ms |
3496 KB |
Output is correct |
| 5 |
Execution timed out |
5042 ms |
8132 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
86 ms |
8808 KB |
Output is correct |
| 7 |
Correct |
76 ms |
8820 KB |
Output is correct |
| 8 |
Correct |
76 ms |
8800 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
154 ms |
5784 KB |
Output is correct |
| 11 |
Correct |
61 ms |
24356 KB |
Output is correct |
| 12 |
Correct |
436 ms |
27816 KB |
Output is correct |
| 13 |
Correct |
499 ms |
27960 KB |
Output is correct |
| 14 |
Correct |
767 ms |
27880 KB |
Output is correct |
| 15 |
Correct |
678 ms |
27880 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
370 ms |
6508 KB |
Output is correct |
| 19 |
Correct |
839 ms |
3496 KB |
Output is correct |
| 20 |
Execution timed out |
5042 ms |
8132 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
