#include "candies.h"
#include <vector>
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2e5 + 5;
int n, q;
vector<pair<int, int>> ev[maxn];
int c[maxn];
struct node {
long long sum;
long long mn;
long long mx;
node() { sum = mn = mx = 0; }
node(long long sum, long long mn, long long mx) : sum(sum), mn(mn), mx(mx) {}
node operator+(const node &o) const {
node res = *this;
res.mx = max(res.mx, res.sum + o.mx);
res.mn = min(res.mn, res.sum + o.mn);
res.sum += o.sum;
return res;
}
} tree[maxn << 2];
void update(int pos, int val, int ind = 1, int l = 1, int r = q) {
if (l == r) {
tree[ind].sum += val;
tree[ind].mn = min(0ll, tree[ind].sum);
tree[ind].mx = max(0ll, tree[ind].sum);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(pos, val, ind << 1, l, mid);
else update(pos, val, ind << 1 | 1, mid + 1, r);
tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}
node get(int x, int y, int ind = 1, int l = 1, int r = q) {
if (l > y || r < x) return node();
if (x <= l and r <= y) {
return tree[ind];
}
int mid = (l + r) >> 1;
return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
}
int walk(int k, int ind = 1, int l = 1, int r = q) {
if (l == r) {
if (tree[ind].sum > k) return k;
if (tree[ind].sum < 0) return 0;
return tree[ind].sum;
}
int mid = (l + r) >> 1;
if (tree[ind << 1 | 1].mx - tree[ind << 1 | 1].mn > k) {
return walk(k, ind << 1 | 1, mid + 1, r);
}
int cur = walk(k, ind << 1, l, mid);
if (cur + tree[ind << 1 | 1].mn < 0) {
return tree[ind << 1 | 1].sum - tree[ind << 1 | 1].mn;
}
if (cur + tree[ind << 1 | 1].mx > k) {
return k - (tree[ind << 1 | 1].mx - tree[ind << 1 | 1].sum);
}
return cur + tree[ind << 1 | 1].sum;
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
n = (int)C.size();
q = (int)L.size();
for (int i = 0; i < n; ++i) {
c[i + 1] = C[i];
}
for (int i = 0; i < q; ++i) {
int l = L[i], r = R[i], v = V[i];
++l, ++r;
ev[l].emplace_back(v, i + 1);
if (r < n) {
ev[r + 1].emplace_back(-v, i + 1);
}
}
vector<int> res;
for (int i = 1; i <= n; ++i) {
for (auto [v, id] : ev[i]) {
update(id, v);
}
res.push_back(walk(c[i]));
}
debug(res);
return res;
}
