#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
const ll INF = (ll)(1e18);
struct segtree
{
vector<ll> smx, smn, sum;
int N;
segtree()
{
N = 1<<18;
smx.assign(2*N,0);
smn.assign(2*N,0);
sum.assign(2*N,0);
}
void upd(ll v, int t, int node, int lx, int rx)
{
if(rx-lx==1)
{
smx[node] = max(0LL, v);
smn[node] = min(0LL, v);
sum[node] = v;
return;
}
int mid = (lx+rx)/2;
if(t<mid) upd(v, t, 2*node, lx, mid);
else upd(v, t, 2*node+1, mid, rx);
sum[node] = sum[2*node]+sum[2*node+1];
smx[node] = max(smx[2*node],sum[2*node]+smx[2*node+1]);
smn[node] = min(smn[2*node],sum[2*node]+smn[2*node+1]);
}
ll get(ll c,int node, int lx, int rx)
{
if(rx-lx==1) return min(max(sum[node], 0LL), c);
int mid = (lx+rx)/2;
if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
ll a = get(c, 2*node, lx, mid);
if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
if(a+smn[2*node+1]<0) return sum[2*node+1]-smn[2*node+1];
return a+sum[2*node+1];
}
} st;
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> final_A; // final array
vector<vector<int>> q(N+1); // q[i] store update at pos i
// +1 to remove ambiguity of index 0
for (int i=0; i<Q; i++) q[l[i]].pb(i+1), q[r[i]+1].pb(-(i+1));
for (int i=0; i<N; i++)
{
for (auto j:q[i])
{
// j is the update position
if (j>0) --j, st.upd(v[j], j, 1, 0, Q);
else j=-j-1, st.upd(0, j, 1, 0, Q);
}
final_A.pb(st.get(c[i], 1, 0, Q));
}
return final_A;
}
