#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1<<19;
vector<ll> smx(MX), smn(MX), st(MX);
void upd(int i, int s, int e, int t, ll v) {
if (s==e) {
smx[i]=max(0ll, v);
smn[i]=min(0ll, v);
st[i]=v;
return ;
}
int m=(s+e)/2;
if (t<=m) upd(i*2, s, m, t, v);
else upd(i*2+1, m+1, e, t, v);
st[i]=st[i*2]+st[i*2+1];
smx[i]=max(smx[i*2], st[i*2]+smx[i*2+1]);
smn[i]=min(smn[i*2], st[i*2]+smn[i*2+1]);
}
ll get(int i, int s, int e, ll c) {
if (s==e) return min(max(st[i], 0ll), c);
int m=(s+e)/2;
if (smx[i*2+1]-smn[i*2+1]>c) return get(i*2+1, m+1, e, c);
ll r=get(i*2, s, m, c);
if (r+smx[i*2+1]>c) return c-(smx[i*2+1]-st[i*2+1]);
if (r+smn[i*2+1]<0) return st[i*2+1]-smn[i*2+1];
return r+st[i*2+1];
}
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> rt;
vector<vector<int>> q(N+1);
for (int i=0; i<Q; i++) q[l[i]].emplace_back(i+1), q[r[i]+1].emplace_back(-(i+1));
for (int i=0; i<N; i++) {
for (auto &j:q[i]) {
if (j>0) j--, upd(1, 0, Q-1, j, v[j]);
else j=-j-1, upd(1, 0, Q-1, j, 0);
}
rt.emplace_back(get(1, 0, Q-1, c[i]));
}
return rt;
}
