#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=2e5+50;
const ll INF=1e18;
int n,q;
vector<array<int,3>>ev[N];
struct Node{ll mn,mx;int imn,imx;};
Node Merge(Node a,Node b){
pair<ll,int>m,M;
if(a.mn<b.mn)m={a.mn,a.imn};
else m={b.mn,b.imn};
if(a.mx>b.mx)M={a.mx,a.imx};
else M={b.mx,b.imx};
return {m.fi,M.fi,m.se,M.se};
}
struct SegTree{
int root,nc,lc[2*N],rc[2*N];ll lazy[2*N];Node node[2*N];
SegTree(){node[0]={INF,-INF,0,0};}
void update(int c,ll x){
node[c].mn+=x;
node[c].mx+=x;
lazy[c]+=x;
}
void push(int c){
update(lc[c],lazy[c]);
update(rc[c],lazy[c]);
lazy[c]=0;
}
void Update(int c,int ss,int se,int qs,int qe,ll x){
if(qs>qe||qe<ss||se<qs)return;
if(qs<=ss&&se<=qe){update(c,x);return;}
int mid=ss+se>>1;push(c);
Update(lc[c],ss,mid,qs,qe,x);
Update(rc[c],mid+1,se,qs,qe,x);
node[c]=Merge(node[lc[c]],node[rc[c]]);
}
Node Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qe<ss||se<qs)return{INF,-INF,0,0};
if(qs<=ss&&se<=qe)return node[c];
int mid=ss+se>>1;push(c);
return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void Build(int &c,int ss,int se){
if(!c)c=++nc,node[c]={0,0,ss,ss};
if(ss==se)return;
int mid=ss+se>>1;
Build(lc[c],ss,mid);
Build(rc[c],mid+1,se);
}
}ST;
vector<int> distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v) {
n=c.size();q=l.size();
vector<int>res;
for(int i=0;i<q;i++){
ev[l[i]].pb({i+1,v[i],1});
ev[r[i]+1].pb({i+1,v[i],0});
}
ST.Build(ST.root,0,q);
for(int i=0;i<n;i++){
for(auto [j,x,type]:ev[i]){
if(type==1)ST.Update(ST.root,0,q,j,q,x);
else ST.Update(ST.root,0,q,j,q,-x);
}
int l=0,r=q,ind=0;
while(l<=r){
int mid=l+r>>1;
Node x=ST.Get(ST.root,0,q,mid,q);
if(x.mx-x.mn>=c[i])ind=mid,l=mid+1;
else r=mid-1;
}
Node x=ST.Get(ST.root,0,q,ind,q);
int ans=0;
if(x.mx-x.mn<c[i]||x.imx==ind){
int ind1=x.imn;
ans=ST.Get(ST.root,0,q,q,q).mn-ST.Get(ST.root,0,q,ind1,ind1).mn;
}
else{
int ind1=x.imx;
ans=c[i]-(ST.Get(ST.root,0,q,ind1,ind1).mn-ST.Get(ST.root,0,q,q,q).mn);
}
res.pb(ans);
}
return res;
}
