////////////////////////////////////////
#include "candies.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=2e5+5;
#define fi first
#define se second
int n,q;
vector<pair<int,int> >qr[N];
const int ts=1<<19;
ll mx[ts];
ll mn[ts];
ll sum[ts];
void pull(int id){
sum[id]=sum[id*2]+sum[id*2+1];
mx[id]=max(mx[id*2],mx[id*2+1]+sum[id*2]);
mn[id]=min(mn[id*2],mn[id*2+1]+sum[id*2]);
}
void upd(int id,int l,int r,int p,ll v){
if(l==r){
mx[id]=0;
mn[id]=0;
sum[id]=v;
if(v>0) mx[id]=v;
else mn[id]=v;
return;
}
int mid=(l+r)/2;
if(p<=mid) upd(id*2,l,mid,p,v);
else upd(id*2+1,mid+1,r,p,v);
pull(id);
}
ll qry(int id,int l,int r,ll v,ll c){
if(l==r){
ll res=v+sum[id];
res=min(res,c);
res=max(res,0LL);
return res;
}
int mid=(l+r)/2;
if(mx[id*2+1]-mn[id*2+1]>=c){
ll res=qry(id*2+1,mid+1,r,v,c);
return res;
}
v=qry(id*2,l,mid,v,c);
if(v+mx[id*2+1]>c){
return c+sum[id*2+1]-mx[id*2+1];
}
if(v+mn[id*2+1]<0){
return sum[id*2+1]-mn[id*2+1];
}
return v+sum[id*2+1];
}
vector<int>distribute_candies(vi c,vi l,vi r,vi v){
n=c.size();q=l.size();
vi ans(n);
for(int i=0; i<q ;i++){
qr[l[i]+1].push_back({i+1,v[i]});
qr[r[i]+2].push_back({i+1,0});
}
for(int i=1; i<=n ;i++){
for(auto c:qr[i]){
upd(1,1,q,c.fi,c.se);
}
ans[i-1]=qry(1,1,q,0,c[i-1]);
}
return ans;
}
//////////////////////////////////////////
