#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long n,a[200069];
vector<pair<long long,long long>> ql[200069];
struct segtree
{
long long l,r,mn,mx,lz;
segtree *p[2];
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
mn=0;
mx=0;
lz=0;
if(l<r)
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
inline void blc()
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->mn+=lz;
p[ii]->mx+=lz;
p[ii]->lz+=lz;
}
lz=0;
}
void ud(long long lh,long long rh,long long w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
mn+=w;
mx+=w;
lz+=w;
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(lh,rh,w);
}
mn=min(p[0]->mn,p[1]->mn);
mx=max(p[0]->mx,p[1]->mx);
}
}
long long qrn(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return inf;
}
else if(l>=lh&&r<=rh)
{
return mn;
}
else
{
blc();
return min(p[0]->qrn(lh,rh),p[1]->qrn(lh,rh));
}
}
long long qrx(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return -inf;
}
else if(l>=lh&&r<=rh)
{
return mx;
}
else
{
blc();
return max(p[0]->qrx(lh,rh),p[1]->qrx(lh,rh));
}
}
}
sg;
vector<int> distribute_candies(vector<int> oa,vector<int> ka,vector<int> la,vector<int> wg)
{
long long t,rr,i,j,k,l,w,sz,mn,mx,mn2,lh,rh,md,zz,z;
vector<int> v;
n=oa.size();
for(i=1;i<=n;i++)
{
a[i]=oa[i-1];
}
t=ka.size();
for(rr=1;rr<=t;rr++)
{
k=ka[rr-1]+1;
l=la[rr-1]+1;
w=wg[rr-1];
ql[k].push_back({rr,w});
ql[l+1].push_back({rr,-w});
}
sg.bd(0,t);
for(i=1;i<=n;i++)
{
sz=ql[i].size();
for(j=0;j<sz;j++)
{
k=ql[i][j].fr;
w=ql[i][j].sc;
sg.ud(k,t,w);
}
if(sg.mx-sg.mn<=a[i])
{
z=sg.qrn(t,t)-sg.mn;
}
else
{
for(lh=1,rh=t;lh<=rh;)
{
md=(lh+rh)/2;
mn=sg.qrn(md,t);
mx=sg.qrx(md,t);
if(mx-mn<=a[i])
{
zz=md;
rh=md-1;
}
else
{
lh=md+1;
}
}
mn=sg.qrn(zz,t);
mx=sg.qrx(zz,t);
mn2=sg.qrn(zz-1,t);
if(mn2<mn)
{
z=a[i]-(mx-sg.qrn(t,t));
}
else
{
z=sg.qrn(t,t)-mn;
}
}
v.push_back(z);
}
return v;
}
