#include "candies.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
using ll = long long;
template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;
struct info {
ll sum, min, max;
};
constexpr info unit = {0, 0, 0};
info merge(const info& l, const info& r) {
return {l.sum + r.sum, std::min(l.min, l.sum + r.min), std::max(l.max, l.sum + r.max)};
}
struct segtree {
int size, logn;
vector<info> data;
explicit segtree(const int n) {
logn = 0;
while ((1 << logn) < n) logn += 1;
size = 1 << logn;
data.resize(2 * size, unit);
}
void set(int i, const info& o) {
i += size;
data[i] = o;
while (i > 1) {
i >>= 1;
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
info prod(int l, int r) const {
l += size;
r += size;
info sl = unit, sr = unit;
while (l < r) {
if (l & 1) sl = merge(sl, data[l++]);
if (r & 1) sr = merge(data[--r], sr);
l >>= 1;
r >>= 1;
}
return merge(sl, sr);
}
info prod() const {
return data[1];
}
template <class F>
pair<int, info> min_left(const F& f) const {
if (f(data[1])) {
return {0, data[1]};
}
info acc = unit;
int k = 1;
while (k < size) {
const int r = 2 * k + 1;
if (f(merge(data[r], acc))) {
acc = merge(data[r], acc);
k <<= 1;
} else {
k = r;
}
}
return {k - size + 1, acc};
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
const int N = C.size();
const int Q = L.size();
vector<vector<int>> enable(N), disable(N);
for (int i = 0; i < Q; ++i) {
enable[L[i]].push_back(i);
disable[R[i]].push_back(i);
}
segtree seg(Q);
vector<int> res(N);
for (int i = 0; i < N; ++i) {
for (const int q : enable[i]) {
seg.set(q, {V[q], std::min(0, V[q]), std::max(0, V[q])});
}
const auto [l, acc] = seg.min_left([&](const info& x) {
return x.max - x.min < C[i];
});
const auto all = seg.prod();
if (l == 0) {
res[i] = all.sum - all.min;
} else if (V[l - 1] > 0) {
const ll high = seg.prod(0, l).sum + acc.max;
res[i] = C[i] - (high - all.sum);
} else {
const ll low = seg.prod(0, l).sum + acc.min;
res[i] = all.sum - low;
}
for (const int q : disable[i]) {
seg.set(q, unit);
}
}
return res;
}
