#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=2*1e5+5;
struct upd
{
long long l,r,v,i;
upd(){}
upd(long long _l,long long _r,long long _v,long long _i)
{
l=_l;
r=_r;
v=_v;
i=_i;
}
bool operator<(const upd&u)const
{
return l<u.l;
}
};
struct segm
{
long long maxx,minn,maxi,mini,sum;
segm(){}
segm(long long x,long long n,long long xi,long long ni,long long s)
{
maxx=x;
minn=n;
maxi=xi;
mini=ni;
sum=s;
}
};
segm t[4*maxn];
void init(long long i,long long l,long long r)
{
if(l==r)
{
t[i].maxi=t[i].mini=l;
return;
}
long long m=(l+r)/2;
init(i*2,l,m);
init(i*2+1,m+1,r);
t[i].maxi=t[i].mini=l;
}
segm pull(segm s1,segm s2)
{
segm s={0,0,0,0,0};
if(s1.maxx>s2.maxx)
{
s.maxx=s1.maxx;
s.maxi=s1.maxi;
}
else
{
s.maxx=s2.maxx;
s.maxi=s2.maxi;
}
if(s1.minn<s2.minn)
{
s.minn=s1.minn;
s.mini=s1.mini;
}
else
{
s.minn=s2.minn;
s.mini=s2.mini;
}
s.sum=s1.sum+s2.sum;
return s;
}
long long lz[4*maxn];
void push(long long i,long long l,long long r)
{
t[i].minn+=lz[i];
t[i].maxx+=lz[i];
t[i].sum+=(r-l+1)*lz[i];
if(l!=r)
{
lz[i*2]+=lz[i];
lz[i*2+1]+=lz[i];
}
lz[i]=0;
}
void update(long long i,long long l,long long r,long long ql,long long qr,long long x)
{
push(i,l,r);
if(ql>qr)return;
if(ql<=l&&r<=qr)
{
lz[i]+=x;
push(i,l,r);
return;
}
long long m=(l+r)/2;
update(i*2,l,m,ql,min(qr,m),x);
update(i*2+1,m+1,r,max(m+1,ql),qr,x);
t[i]=pull(t[i*2],t[i*2+1]);
}
segm query(long long i,long long l,long long r,long long ql,long long qr)
{
push(i,l,r);
if(ql>qr)return {(long long)-1e18,(long long)1e18,0,0,0};
if(ql<=l&&r<=qr)return t[i];
long long m=(l+r)/2;
return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr));
}
upd u[maxn];
vector<upd> q[maxn];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
for(long long i=0;i<l.size();i++)
u[i]={l[i],r[i],v[i],i};
sort(u,u+l.size());
vector<int> ans(c.size());
init(1,0,l.size());
long long j=0;
long long sum=0;
for(long long i=0;i<c.size();i++)
{
while(j<l.size()&&u[j].l==i)
{
//cout<<"+ "<<u[j].i<<" "<<j<<endl;
sum+=u[j].v;
update(1,0,l.size()-1,u[j].i,l.size()-1,u[j].v);
q[u[j].r+1].push_back(u[j]);
j++;
}
for(long long j=0;j<q[i].size();j++)
{
//cout<<"- "<<q[i][j].i<<endl;
sum-=q[i][j].v;
update(1,0,l.size()-1,q[i][j].i,l.size()-1,-q[i][j].v);
}
long long wall=-1,tp=0;
long long lf=0,rt=c.size()-1;
while(lf<=rt)
{
long long m=(lf+rt)/2;
segm s=query(1,0,l.size()-1,m,l.size()-1);
//cout<<m<<": "<<s.minn<<" "<<s.maxx<<" "<<s.mini<<" "<<s.maxi<<endl;
if(s.maxx-s.minn>=c[i])
{
//cout<<"in "<<endl;
if(s.maxi>s.mini)wall=s.maxi,tp=1;
else wall=s.mini,tp=0;
lf=m+1;
}
else rt=m-1;
}
//cout<<sum<<endl;
if(wall==-1)
{
wall=0;
segm s=query(1,0,l.size()-1,0,l.size()-1);
if(s.minn<0&&-s.minn>=c[i])wall=s.minn;
if(s.maxx>0&&s.maxx>=c[i])wall=s.maxx-c[i];
ans[i]=sum-wall;
continue;
}
//cout<<c[i]<<" > "<<wall<<endl;
wall=query(1,0,l.size()-1,wall,wall).sum;
if(tp==1)wall-=c[i];
ans[i]=sum-wall;
//cout<<i<<" "<<sum<<" "<<wall<<endl;
}
return ans;
}
