#include "candies.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int N = 2e5+5;
vector<int> add[N], rem[N];
int arr[N];
struct node{
ll mx, mn, sum;
node(){
mx = mn = sum = 0;
}
node(int v){
mx = max(0, v);
mn = min(0, v);
sum = v;
}
}s[N<<2];
node merge(node x, node y){
node z;
z.sum = x.sum + y.sum;
z.mn = min(y.mn, x.mn + y.sum);
z.mx = max(y.mx, x.mx + y.sum);
return z;
}
void upd(int p, int v, int nd, int x, int y){
if (x == y){
arr[p] = v;
s[nd] = node(v);
return;
}
int mid = (x+y) >> 1;
if (p <= mid)
upd(p, v, nd << 1, x, mid);
else
upd(p, v, nd<<1|1, mid+1, y);
s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}
node get(int l, int r, int nd, int x, int y){
if (l > y or x > r)
return node();
if (l <= x and y <= r)
return s[nd];
int mid = (x+y) >> 1;
return merge(get(l, r, nd<<1, x, mid), get(l, r, nd<<1|1, mid+1, y));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
vector<int> s(n);
for (int i = 0; i < q; i++){
add[l[i]].push_back(i);
rem[r[i]].push_back(i);
}
for (int i = 0; i < n; i++){
for (auto pos: add[i])
upd(pos, v[pos], 1, 0, q-1);
int st = -1, en = q-1;
while (st < en){
int mid = (st + en + 1) >> 1;
node res = get(mid, q-1, 1, 0, q-1);
if (res.mx - res.mn > c[i])
st = mid;
else
en = mid-1;
}
node res = get(max(st, 0), q-1, 1, 0, q-1);
if (st >= 0){
if (arr[st] > 0)
s[i] = c[i] + res.mn;
else
s[i] = res.mx;
}
else
s[i] = res.mx;
for (auto pos: rem[i])
upd(pos, 0, 1, 0, q-1);
}
return s;
}
