#include "candies.h"
#include <vector>
using namespace std;
#define pb push_back
using ll=long long;
struct titem { ll sum, rmax, rmin; };
const int M = 262144;
titem tree[M<<1];
void upd(int up, titem &&uv, int ti, int tl, int tr) {
if (tl == tr) { tree[ti] = uv; return; }
int md = (tl+tr)/2;
if (up <= md) upd(up, move(uv), ti*2, tl, md);
else upd(up, move(uv), ti*2+1, md+1, tr);
tree[ti].sum = tree[ti*2].sum + tree[ti*2+1].sum;
tree[ti].rmax = max(tree[ti*2].rmax + tree[ti*2+1].sum, tree[ti*2+1].rmax);
tree[ti].rmin = min(tree[ti*2].rmin + tree[ti*2+1].sum, tree[ti*2+1].rmin);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
vector<vector<int>> events(n+1);
for (int i=0; i<q; ++i) { events[l[i]].pb(i); events[r[i]+1].pb(i); }
vector<int> ans(n);
for (int i=0; i<n; ++i) {
for (int qi: events[i]) {
if (i == l[qi]) {
upd(qi, titem{v[qi], max(0, v[qi]), min(0, v[qi])}, 1, 0, q-1);
} else {
upd(qi, titem{0, 0, 0}, 1, 0, q-1);
}
}
int ti=1, tl=0, tr=q-1;
ll brsum = 0, brmax = 0, brmin = 0;
while (tl < tr) {
int md = (tl+tr)/2;
if (max(brsum + tree[ti*2+1].rmax, brmax)-
min(brsum + tree[ti*2+1].rmin, brmin) <= c[i]) {
brmax = max(brmax, brsum + tree[ti*2+1].rmax);
brmin = min(brmin, brsum + tree[ti*2+1].rmin);
brsum += tree[ti*2+1].sum;
ti *= 2;
tr = md;
} else {
ti = ti*2+1;
tl = md+1;
}
}
if (max(brsum + tree[ti].rmax, brmax) - min(brsum + tree[ti].rmin, brmin) <= c[i]) {
ans[i] = tree[1].sum;
} else {
if (v[tl] > 0) {
ans[i] = c[i] + brsum;
} else {
ans[i] = brsum;
}
}
}
return ans;
}
