#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
ll n, m, q;
pll d[1000001];
ll tt[1000001];
void build(int h,int l,int r)
{
if (l==r)
{
d[h]=mp(0, 0);
return;
}
int w=(l+r)/2;
build(h*2,l,w);
build(h*2+1,w+1,r);
d[h]=mp(0, 0);
}
void push(int h)
{
if (tt[h])
{
d[h*2].fi+=tt[h];
d[h*2].se+=tt[h];
d[h*2+1].fi+=tt[h];
d[h*2+1].se+=tt[h];
tt[h*2]+=tt[h];
tt[h*2+1]+=tt[h];
tt[h]=0;
}
}
void update(int h,int l,int r,int x,int y,int k)
{
if (x>y) return;
if (l==x && y==r)
{
d[h].fi+=k;
d[h].se+=k;
tt[h]+=k;
return;
}
push(h);
int w=(l+r)/2;
update(h*2,l,w,x,min(y,w),k);
update(h*2+1,w+1,r,max(x,w+1),y,k);
d[h].fi=min(d[h*2].fi,d[h*2+1].fi);
d[h].se=max(d[h*2].se,d[h*2+1].se);
}
ll get_min(int h,int l,int r,int x,int y)
{
if (x>y) return 1e18;
if (l==x && y==r) return d[h].fi;
int w=(l+r)/2;
push(h);
return min(get_min(h*2,l,w,x,min(y,w)), get_min(h*2+1,w+1,r,max(x,w+1),y));
}
ll get_max(int h,int l,int r,int x,int y)
{
if (x>y) return -1e18;
if (l==x && y==r) return d[h].se;
int w=(l+r)/2;
push(h);
return max(get_max(h*2,l,w,x,min(y,w)), get_max(h*2+1,w+1,r,max(x,w+1),y));
}
ll get(int h,int l,int r,int x)
{
if (l==r)
{
return d[h].fi;
}
int w=(l+r)/2;
push(h);
if (x<=w) return get(h*2,l,w,x); else return get(h*2+1,w+1,r,x);
}
vector<pll> gg[1000001];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n=c.size();
q=l.size();
for (int i = 0; i < q; i++)
{
gg[l[i]].pb(mp(i, v[i]));
gg[r[i]+1].pb(mp(i, -v[i]));
}
vector<int> ans;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < gg[i].size(); j++)
{
update(1,0,q,gg[i][j].fi+1,q,gg[i][j].se);
}
//cout << i << " " << d[1].fi << " " << d[1].se << "\n";
if (d[1].se-d[1].fi<c[i])
{
ans.pb(get(1,0,q,q)-get_min(1,0,q,0,q));
continue;
}
ll l=0, r=q;
while (l<r)
{
int w=(l+r+1)/2;
if (get_max(1,0,q,w,q)-get_min(1,0,q,w,q)>=c[i]) l=w; else r=w-1;
}
//cout << i << " :\n";
//cout << " l : " << l << "\n";
ll o1=get(1,0,q,l), o2=get(1,0,q,q);
//cout << " " << o1 << "\n";
//cout << " " << o2 << "\n";
assert(o1!=o2);
if (o1<o2)
{
ll o3=get_max(1,0,q,l+1,q);
ans.pb(c[i]-(o3-o2));
}else
{
ll o3=get_min(1,0,q,l+1,q);
ans.pb(o2-o3);
}
}
return ans;
}
