#include <bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
template<typename T>
using vec = vector<T>;
const int maxN = 2e5 + 5;
struct Push {
int to_add;
bool set_0;
bool set_mx;
};
Push combine_push(const optional<Push> &att, const Push &b) {
if (b.set_0)
return b;
if (b.set_mx)
return b;
if (!att.has_value())
return b;
auto a = *att;
if (a.set_0)
return b;
if (a.set_mx)
return b;
return {a.to_add + b.to_add, false, false};
}
vec<i32> tc;
int stree[maxN];
optional<Push> pushes[4 * maxN + 5];
void build() {
memset(stree, 0, sizeof stree);
for (int i = 0; i < 4 * maxN + 5; i++)pushes[i] = nullopt;
}
void push(int v, int tl, int tr) {
if (!pushes[v].has_value()) return;
if (tl != tr) {
pushes[2 * v] = combine_push(pushes[2 * v], *pushes[v]);
pushes[2 * v + 1] = combine_push(pushes[2 * v + 1], *pushes[v]);
int tm = (tl + tr) / 2;
if (tl == tm) {
if (pushes[2 * v].has_value()) {
if (pushes[2 * v]->set_0) {
stree[tl] = 0;
} else if (pushes[2 * v]->set_mx) {
stree[tl] = tc[tl];
} else {
stree[tl] += pushes[v]->to_add;
}
}
}
if (tm + 1 == tr) {
if (pushes[2 * v + 1].has_value()) {
if (pushes[2 * v + 1]->set_0) {
stree[tr] = 0;
} else if (pushes[2 * v + 1]->set_mx) {
stree[tr] = tc[tr];
} else {
stree[tr] += pushes[v]->to_add;
}
}
}
}
pushes[v] = nullopt;
}
int get(int v, int tl, int tr, int pos) {
push(v, tl, tr);
if (tl == tr) {
return stree[tl];
}
int tm = (tl + tr) / 2;
if (pos <= tm)
return get(v * 2, tl, tm, pos);
else
return get(v * 2 + 1, tm + 1, tr, pos);
}
void update(int v, int tl, int tr, int l, int r, Push p) {
push(v, tl, tr);
if (tl == l and tr == r) {
pushes[v] = p;
if (l == r) {
if (pushes[v].has_value()) {
if (pushes[v]->set_0) {
stree[tr] = 0;
} else if (pushes[v]->set_mx) {
stree[tr] = tc[tr];
} else {
stree[tr] += pushes[v]->to_add;
}
}
}
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
if (r <= tm)
update(v * 2, tl, tm, l, r, p);
else if (l > tm)
update(v * 2 + 1, tm + 1, tr, l, r, p);
else
update(v * 2, tl, tm, l, tm, p), update(v * 2 + 1, tm + 1, tr, tm + 1, r, p);
}
vec<i32> distribute_candies(vec<i32> C, vec<i32> L, vec<i32> R, vec<i32> V) {
int n = len(C);
vec<pair<int, int>> rc(n);
for (int i = 0; i < n; i++) {
rc[i] = {C[i], i};
}
sort(all(rc));
sort(all(C));
tc = C;
build();
for (int i = 0; i < len(L); i++) {
int v = V[i];
if (v == 0)continue;
if (v > 0) {
if (get(1, 0, n - 1, 0) + v <= C[0]) {
update(1, 0, n - 1, 0, n - 1, Push{v, false, false});
} else {
int tl = 0;
int tr = n - 1;
while (tl != tr) {
int tm = (tl + tr+1) / 2;
if ((get(1, 0, n - 1, tm) + v > C[tm])) {
tl = tm;
} else {
tr = tm - 1;
}
}
update(1, 0, n - 1, 0, tl, Push{0, false, true});
if (tl != n - 1) {
update(1, 0, n - 1, tl + 1, n - 1, Push{v, false, false});
}
}
} else {
if (get(1, 0, n - 1, 0) + v >= 0) {
update(1, 0, n - 1, 0, n - 1, Push{v, false, false});
} else {
int tl = 0;
int tr = n - 1;
while (tl != tr) {
int tm = (tl + tr + 1) / 2;
if (get(1, 0, n - 1, tm) + v < 0) {
tl = tm;
} else {
tr = tm - 1;
}
}
update(1, 0, n - 1, 0, tl, Push{0, true, false});
if (tl != n - 1) {
update(1, 0, n - 1, tl + 1, n - 1, Push{v, false, false});
}
}
}
}
vec<i32> ans(n);
for (int i = 0; i < n; i++) {
ans[rc[i].second] = get(1, 0, n - 1, i);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1880 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
482 ms |
25296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1880 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1880 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
