#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, tim;
bool L = 0, R = 0;
nodo *l = nullptr, *r = nullptr;
};
nodo *seg = new nodo();
nodo *roots[MAXQ];
vector<ll> I, D;
ll n, act = 1, pot=1;
void create(nodo *&a, nodo *b)
{
if(b==nullptr)
b=new nodo();
a = new nodo(*b);
a->R=a->L=0;
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)
{
nodo *l, *r;
if(!(nod->L)||nod->l==nullptr)
{
create(l,nod->l);
nod->l=l;
nod->L=1;
}
if(!(nod->R)||nod->r==nullptr)
{
create(r,nod->r);
nod->r=r;
nod->R=1;
}
upd(nod->l, nod);
upd(nod->r, nod);
nod->ma=MIN;
nod->mi=INF;
nod->lazy=0;
}
void update(nodo *nod, ll l, ll r, ll a, ll b, ll x)
{
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);
ll mid=(l+r)/2;
update(nod->l,l,mid,a,b,x);
update(nod->r,mid+1,r,a,b,x);
}
ll calc(nodo *nod, ll l, ll r, ll a, ll b)
{
if(l>b||r<a)
return 0;
if(a<=l&&r<=b)
return nod->lazy;
prop(nod);
ll mid=(l+r)/2;
return calc(nod->l,l,mid,a,b)+calc(nod->r,mid+1,r,a,b);
}
ll calcMi(nodo *nod, ll l, ll r, ll a, ll b)
{
if(l>b||r<a)
return INF;
if(a<=l&&r<=b)
return nod->mi;
prop(nod);
ll mid=(l+r)/2;
return min(calcMi(nod->l,l,mid,a,b),calcMi(nod->r,mid+1,r,a,b));
}
ll calcMa(nodo *nod, ll l, ll r, ll a, ll b)
{
if(l>b||r<a)
return MIN;
if(a<=l&&r<=b)
return nod->ma;
prop(nod);
ll mid=(l+r)/2;
return max(calcMa(nod->l,l,mid,a,b),calcMa(nod->r,mid+1,r,a,b));
}
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;
seg->tim = act++;
ll 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++)
{
update(seg,0,pot-1,i,i,fin[i]);
}
for (i = sz(l)-1; i >=0; i--)
{
roots[i]=new nodo();
if (i<sz(l)-1)
create(roots[i], roots[i + 1]);
else
create(roots[i], seg);
update(roots[i],0,pot-1,l[i], r[i], -v[i]);
}
roots[sz(r)]=seg;
vector<int>ans(sz(c));
for(i=0; i<sz(c); i++)
{
ll L=0, R=sz(r), piv, pos=sz(r), j;
while(L<=R)
{
piv=(L+R)/2;
if(calcMa(roots[piv],0,pot-1,i,i)-calcMi(roots[piv],0,pot-1,i,i)>=1ll*c[i])
{
L=piv+1;
pos=piv;
}
else
R=piv-1;
}
if(calc(roots[pos],0,pot-1,i,i)==calcMi(roots[pos],0,pot-1,i,i))
ans[i]=c[i]-int(calcMa(roots[pos],0,pot-1,i,i)-fin[i]);
else
ans[i]=int(fin[i]-calcMi(roots[pos],0,pot-1,i,i));
/*cout << i << '\n';
for(j=0; j<=sz(r); j++)
{
cout << calcMa(roots[j],0,pot-1,i,i) << ' ' << calcMi(roots[j],0,pot-1,i,i) << '\n';
}
cout << '\n';*/
}
return ans;
}
