#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
const long long N=1000000000000000000LL,S=800003,T=800004;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,C[200009],L[200009],R[200009],V[200009],f[200009],pi,F[200009],mn,mx,l,r,z,za,seg[800009],segmn[800009],segmx[800009],lef,rig,mid;
pair <long long, long long> p[800009];
vector <int> ans;
void upd(int rr){
if(rr==0) return;
seg[rr]=seg[rr*2]+seg[rr*2+1];
segmn[rr]=min(segmn[rr*2],seg[rr*2]+segmn[rr*2+1]);
segmx[rr]=max(segmx[rr*2],seg[rr*2]+segmx[rr*2+1]);
upd(rr/2);
}
void UPD(int q){
seg[q+za-1]=f[q];
segmn[q+za-1]=f[q];
segmx[q+za-1]=f[q];
upd((q+za-1)/2);
}
void read(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg[T]=seg[S]+seg[rr];
segmn[T]=min(segmn[S],seg[S]+segmn[rr]);
segmx[T]=max(segmx[S],seg[S]+segmx[rr]);
swap(seg[S],seg[T]);swap(segmn[S],segmn[T]);swap(segmx[S],segmx[T]);
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
vector<int> distribute_candies(vector<int> Cc, vector<int> Ll, vector<int> Rr, vector<int> Vv) {
a=Cc.size();tes=Ll.size();ans.resize(a);
for(i=1; i<=a; i++){
C[i]=Cc[i-1];
}
L[1]=1;R[1]=a;V[1]=N;
L[2]=1;R[2]=a;V[2]=-N;tes+=2;
for(t=3; t<=tes; t++){
L[t]=Ll[t-3]+1;R[t]=Rr[t-3]+1;V[t]=Vv[t-3];
}
for(t=1; t<=tes; t++){
pi++;p[pi]={L[t],t};pi++;p[pi]={R[t]+1,-t};
}
sort(p+1,p+pi+1);
za=1;
while(za<tes) za*=2;
int ee=1;
for(i=1; i<=a; i++){
while(ee<=pi&&p[ee].first<=i){
ii=p[ee].second;
if(ii>0){
f[ii]=V[ii];
UPD(ii);
}else{
f[-ii]=0;
UPD(-ii);
}
ee++;
}
mn=N;mx=-N;
lef=0;rig=tes+1;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
l=mid;r=tes;seg[S]=0;segmn[S]=N;segmx[S]=-N;
read(1,za,1);mn=segmn[S];mx=segmx[S];
if(mx-mn>=C[i]){
lef=mid;
}else{
rig=mid;
}
}
mid=lef;
l=mid;r=tes;seg[S]=0;segmn[S]=N;segmx[S]=-N;
read(1,za,1);mn=segmn[S];mx=segmx[S];
//
zx=seg[1];
l=1;r=mid;seg[S]=0;segmn[S]=N;segmx[S]=-N;
read(1,za,1);xc=seg[S];
e=xc-f[mid];
mn+=e;mx+=e;
//
if(mx-mn>=C[i]){
if(xc==mn){
ans[i-1]=C[i]+(zx-mx);
}else{
ans[i-1]=zx-mn;
}
}
}
return ans;
}
