#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sts = 1;
vector < ll > pf;
vector < pair < ll, ll > > stn, stx;
void
pfa (ll i, ll x)
{
while (i < pf.size ())
{
pf[i] += x;
i += (i + 1) & -(i + 1);
}
}
ll
pfs (ll i)
{
ll sum = 0;
while (i >= 0)
{
sum += pf[i];
i -= (i + 1) & -(i + 1);
}
return sum;
}
void
stp (auto &st, int i)
{
if (i < sts)
{
st[i * 2].first += st[i].second;
st[i * 2].second += st[i].second;
st[i * 2 + 1].first += st[i].second;
st[i * 2 + 1].second += st[i].second;
}
st[i].second = 0;
}
void
sta1 (auto &st, ll i, int j, ll x, ll n, ll l, ll r, bool c)
{
if (j < l || r < i) return;
if (i <= l && r <= j)
{
st[n].first += x, st[n].second += x;
return;
}
stp (st, n);
int m = (l + r + 1) / 2;
sta1 (st, i, j, x, n * 2, l, m - 1, c);
sta1 (st, i, j, x, n * 2 + 1, m, r, c);
st[n].first = (c
? max (st[n * 2].first, st[n * 2 + 1].first)
: min (st[n * 2].first, st[n * 2 + 1].first));
}
void
sta (ll i, ll x)
{
pfa (i, x);
sta1 (stn, i, sts - 1, x, 1, 0, sts - 1, false);
sta1 (stx, i, sts - 1, x, 1, 0, sts - 1, true);
}
ll
stnx1 (auto &st, ll i, ll j, ll n, ll l, ll r, bool c)
{
assert (!(j < l || r < i));
if (i <= l && r <= j) return st[n].first;
stp (st, n);
ll m = (l + r + 1) / 2;
if (j < m) return stnx1 (st, i, j, n * 2, l, m - 1, c);
if (m <= i) return stnx1 (st, i, j, n * 2 + 1, m, r, c);
ll x = stnx1 (st, i, j, n * 2, l, m - 1, c);
ll y = stnx1 (st, i, j, n * 2 + 1, m, r, c);
return (c ? max (x, y) : min (x, y));
}
ll
stnx (ll i, bool c)
{
return stnx1 ((c ? stx : stn), 0, i, 1, 0, sts - 1, c);
}
ll
tst1 (ll x, ll n, ll l, ll r, ll mn, ll mx)
{
if (n >= sts) return l;
stp (stn, n);
stp (stx, n);
ll mn2 = min (mn, stn[n * 2].first), mx2 = max (mx, stx[n * 2].first), m = (l + r + 1) / 2;
if (mx2 - mn2 >= x)
return tst1 (x, n * 2, l, m - 1, mn, mx);
else
return tst1 (x, n * 2 + 1, m, r, mn2, mx2);
}
ll
tst (ll x)
{
return tst1 (x, 1, 0, sts - 1, 0, 0);
}
std::vector<int> distribute_candies (std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v)
{
ll n = c.size();
v.push_back (0);
l.push_back (0);
r.push_back (-1);
vector < ll > a;
for (auto &x : v) a.push_back (x);
reverse (a.begin (), a.end ());
reverse (l.begin (), l.end ());
reverse (r.begin (), r.end ());
a.push_back (-1e18);
l.push_back (0);
r.push_back (n - 1);
for (auto &x : a) x *= -1;
vector < vector < pair < ll, ll > > > ea (n + 1);
for (int i = 0; i < a.size (); ++i)
ea[l[i]].push_back ({ i, a[i] }),
ea[r[i] + 1].push_back ({ i, -a[i] });
while (sts < a.size ()) sts *= 2;
stn.resize (sts * 2);
stx.resize (sts * 2);
pf.resize (a.size ());
vector < int > ans (n);
for (int i = 0; i < n; ++i)
{
for (auto &x : ea[i]) sta (x.first, x.second);
int j = tst (c[i]);
if (pfs (j) == stnx (j, false))
ans[i] = c[i] - stnx (j, true);
else
ans[i] = -stnx (j, false);
}
return ans;
}
