#include "candies.h"
#include <bits/stdc++.h>
typedef std::vector<int> ivec;
#define int long long
ivec c;
int N;
struct node {
int min, max;
node *left, *right;
int maxV, maxC;
int delta;
enum Set {
zero, cap, none
} set;
node(int l, int r) {
min = l;
max = r;
maxV = 0;
maxC = c[r - 1];
delta = 0;
set = none;
if (r == l + 1) {
left = right = nullptr;
return;
} else {
left = new node(l, (l + r) / 2);
right = new node((l + r) / 2, r);
}
}
void add(int l, int r, int x) {
l = std::max(l, min);
r = std::min(r, max);
if (l >= max || r <= min || l >= r) return;
if (l == min && r == max) {
delta += x;
maxV += x;
maxC -= x;
return;
}
push(false);
left->add(l, r, x);
right->add(l, r, x);
maxV = std::max(left->maxV, right->maxV) + delta;
maxC = std::max(left->maxC, right->maxC) - delta;
}
void push(bool d) {
if (set == zero) {
left->set0(min, max);
right->set0(min, max);
set = none;
}
if (set == cap) {
left->setc(min, max);
right->setc(min, max);
set = none;
}
if (d) {
if (delta != 0) {
left->add(min, max, delta);
right->add(min, max, delta);
delta = 0;
}
}
}
void set0(int l, int r) {
l = std::max(l, min);
r = std::min(r, max);
if (l >= max || r <= min || l >= r) return;
if (l == min && r == max) {
set = zero;
maxV = 0;
maxC = c[r - 1];
delta = 0;
return;
}
if (set == zero && delta == 0) return;
push(true);
left->set0(l, r);
right->set0(l, r);
maxV = std::max(left->maxV, right->maxV);
maxC = std::max(left->maxC, right->maxC);
}
void setc(int l, int r) {
l = std::max(l, min);
r = std::min(r, max);
if (l >= max || r <= min || l >= r) return;
if (l == min && r == max) {
set = cap;
maxV = c[r - 1];
maxC = 0;
delta = 0;
return;
}
if (set == cap && delta == 0) return;
push(true);
left->setc(l, r);
right->setc(l, r);
maxV = std::max(left->maxV, right->maxV);
maxC = std::max(left->maxC, right->maxC);
}
int pfxC(int x) {
if (maxC <= x) return max;
if (max == min + 1) return min;
push(true);
if (left->maxC > x) return left->pfxC(x + delta);
return right->pfxC(x + delta);
}
int pfxV(int x) {
if (maxV <= x) return max;
if (max == min + 1) return min;
push(true);
if (left->maxV > x) return left->pfxV(x - delta);
return right->pfxV(x - delta);
}
int query(int x) const {
if (x < min || x >= max) return 0;
if (set == zero) return delta;
if (set == cap) return c[x] + delta;
if (max == min + 1) return delta;
return left->query(x) + right->query(x) + delta;
}
};
ivec distribute_candies(ivec _c, ivec l,
ivec r, ivec v) {
c = std::move(_c);
N = c.size();
int Q = l.size();
ivec ans(N);
bool complete = true;
for (int i = 0; i < Q; ++i) {
if (l[i] != 0 || r[i] != N - 1) complete = false;
}
if (complete) {
ivec realC = c;
std::sort(c.begin(), c.end());
std::map<int, int> posmap;
for (int i = 0; i < N; ++i) {
posmap[c[i]] = i;
}
node tree(0, N);
for (int i = 0; i < Q; ++i) {
if (v[i] > 0) {
int pre = tree.pfxC(v[i]);
tree.setc(0, pre);
tree.add(pre, N, v[i]);
} else if (v[i] < 0) {
int pre = tree.pfxV(-v[i]);
tree.set0(0, pre);
tree.add(pre, N, v[i]);
}
#ifdef LOCAL
std::cout << "Applied operation, tree is now:";
for (int j = 0; j < N; ++j) {
std::cout << " " << tree.query(j);
}
std::cout << std::endl;
#endif
}
for (int i = 0; i < N; ++i) {
ans[i] = tree.query(posmap[realC[i]]);
}
return ans;
}
if (N * Q <= 2000 * 2000) {
for (int i = 0; i < N; ++i) {
int val = 0;
for (int j = 0; j < Q; ++j) {
if (l[j] > i || r[j] < i) continue;
val += v[j];
if (val < 0) val = 0;
if (val > c[i]) val = c[i];
}
ans[i] = val;
}
return ans;
}
bool pos = true;
for (int i = 0; i < Q; ++i) {
if (v[i] < 0) pos = false;
}
if (pos) {
int diff[N + 1];
for (int i = 0; i <= N; ++i) {
diff[i] = 0;
}
for (int i = 0; i < Q; ++i) {
diff[l[i]] += v[i];
diff[r[i] + 1] -= v[i];
}
for (int i = 1; i <= N; ++i) {
diff[i] += diff[i - 1];
}
for (int i = 0; i < N; ++i) {
ans[i] = (signed) std::min<int>(diff[i], c[i]);
}
return ans;
}
assert(false);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
8 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
9040 KB |
Output is correct |
| 2 |
Correct |
77 ms |
8904 KB |
Output is correct |
| 3 |
Correct |
77 ms |
8948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
46 ms |
9968 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
109 ms |
5584 KB |
Output is correct |
| 4 |
Correct |
136 ms |
42068 KB |
Output is correct |
| 5 |
Correct |
312 ms |
45052 KB |
Output is correct |
| 6 |
Correct |
322 ms |
51008 KB |
Output is correct |
| 7 |
Correct |
309 ms |
51848 KB |
Output is correct |
| 8 |
Correct |
299 ms |
48468 KB |
Output is correct |
| 9 |
Correct |
132 ms |
44692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
8 ms |
348 KB |
Output is correct |
| 6 |
Correct |
81 ms |
9040 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8904 KB |
Output is correct |
| 8 |
Correct |
77 ms |
8948 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Runtime error |
46 ms |
9968 KB |
Execution killed with signal 6 |
| 11 |
Halted |
0 ms |
0 KB |
- |
