#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
ll INF = 1e15, MIN=-1e15;
const int MAXQ = 2e5 + 1;
struct nodo
{
ll mi = INF, ma = MIN, lazy = 0;
int tim;
nodo *l = nullptr, *r = nullptr;
};
nodo *roots[MAXQ];
int n, act = 1, pot=1;
void create(nodo *&a, nodo *&b)
{
if(b==nullptr)
a=new nodo();
else
a = new nodo(*b);
a->tim=act++;
}
void upd(nodo *&a, nodo *&nod)
{
a->ma=max(a->ma,a->lazy+nod->ma);
a->mi=min(a->mi,a->lazy+nod->mi);
a->lazy+=nod->lazy;
}
void prop(nodo *&nod)
{
if(nod->l==nullptr||(((nod->l)->tim)<(nod->tim)))
create(nod->l,nod->l);
if(nod->r==nullptr||(((nod->r)->tim)<(nod->tim)))
create(nod->r,nod->r);
upd(nod->l, nod);
upd(nod->r, nod);
nod->ma=MIN;
nod->mi=INF;
nod->lazy=0;
}
int a, b;
ll x;
void update(nodo *&nod, ll l, ll r)
{
if(l>b||r<a)
return;
if(a<=l&&r<=b)
{
nod->lazy+=x;
nod->ma=max(nod->ma,nod->lazy);
nod->mi=min(nod->mi,nod->lazy);
return;
}
prop(nod);
update(nod->l,l,(l+r)/2);
update(nod->r,(l+r)/2+1,r);
}
ll calc(nodo *&nod, ll l, ll r)
{
if(l>b||r<a)
return 0;
if(a<=l&&r<=b)
return nod->lazy;
prop(nod);
return calc(nod->l,l,(l+r)/2)+calc(nod->r,(l+r)/2+1,r);
}
ll calcMi(nodo *&nod, ll l, ll r)
{
if(l>b||r<a)
return INF;
if(a<=l&&r<=b)
return nod->mi;
prop(nod);
return min(calcMi(nod->l,l,(l+r)/2),calcMi(nod->r,(l+r)/2+1,r));
}
ll calcMa(nodo *&nod, ll l, ll r)
{
if(l>b||r<a)
return MIN;
if(a<=l&&r<=b)
return nod->ma;
prop(nod);
return max(calcMa(nod->l,l,(l+r)/2),calcMa(nod->r,(l+r)/2+1,r));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v)
{
n = sz(c);
while(pot<n)
pot*=2;
roots[sz(r)]=new nodo();
roots[sz(r)]->tim = act++;
int i;
vector<ll>fin(sz(c)+1,0);
for(i=0; i<sz(l); i++)
{
fin[l[i]]+=v[i];
fin[r[i]+1]-=v[i];
}
for(i=1; i<sz(c); i++)
fin[i]+=fin[i-1];
for(i=0; i<sz(c); i++)
{
b=a=i;
x=fin[i];
update(roots[sz(r)],0,pot-1);
}
for (i = sz(l)-1; i >=0; i--)
{
roots[i]=new nodo();
create(roots[i], roots[i + 1]);
a=l[i];
b=r[i];
x=-v[i];
update(roots[i],0,pot-1);
}
vector<int>ans(sz(c));
int L, R, piv, pos, j;
ll rec;
for(i=0; i<sz(c); i++)
{
L=0;
R=sz(r);
pos=0;
b=a=i;
rec=calcMi(roots[0],0,pot-1);
if(calcMa(roots[0],0,pot-1)-rec<1ll*c[i])
{
ans[i]=fin[i]-rec;
continue;
}
while(L<=R)
{
piv=(L+R)/2;
if(calcMa(roots[piv],0,pot-1)-calcMi(roots[piv],0,pot-1)>=1ll*c[i])
{
L=piv+1;
pos=piv;
}
else
R=piv-1;
}
rec=calcMi(roots[pos],0,pot-1);
if(calc(roots[pos],0,pot-1)==rec)
ans[i]=c[i]-int(calcMa(roots[pos],0,pot-1)-fin[i]);
else
ans[i]=int(fin[i]-rec);
}
return ans;
}
