#include "candies.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, q;
int ro[maxn];
long long a[maxn];
long long p[maxn];
pair < long long , long long > tmax[maxn * 4], tmin[maxn * 4];
void build(long long i, long long l, long long r)
{
if(l == r)
{
tmin[i] = make_pair(p[l], l);
tmax[i] = make_pair(p[l], l);
return;
}
long long mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
tmin[i] = min(tmin[2*i], tmin[2*i+1]);
tmax[i] = max(tmax[2*i], tmax[2*i+1]);
}
long long ql, qr;
pair < long long, long long> query_max(long long i, long long l, long long r)
{
if(l > r)return make_pair(-1e17, -1);
if(qr < l || ql > r)return make_pair(-1e17, -1);
if(ql <= l && r <= qr)return tmax[i];
long long mid = (l + r)/2;
return max(query_max(2*i, l, mid), query_max(2*i+1, mid+1, r));
}
pair < long long, long long> query_min(long long i, long long l, long long r)
{
if(l > r)return make_pair(1e17, -1);
if(qr < l || ql > r)return make_pair(1e17, -1);
if(ql <= l && r <= qr)return tmin[i];
long long mid = (l + r)/2;
return min(query_min(2*i, l, mid), query_min(2*i+1, mid+1, r));
}
long long suff[maxn];
int nxtp[maxn], nxtn[maxn];
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();
std::vector<int> s;
/// fix l and r
for (int i = 1; i <= n; ++ i)
ro[i] = c[i-1];
for (int i = 1; i <= q; ++ i)
{
a[i] = v[i-1];
}
suff[q+1] = 0;
int np = q+1, nn = q+1;
for (int i = q; i >= 0; -- i)
{
if(a[i] > 0)np = i;
else nn = i;
suff[i] = suff[i+1] + a[i];
nxtp[i] = np;
nxtn[i] = nn;
}
p[0] = 0;
for (int i = 1; i <= q; ++ i)
p[i] = p[i-1] + a[i];
build(1, 0, q);
for (int i = 1; i <= n; ++ i)
{
int lt = 0, rt = q, mid, ans = -1;
while(lt <= rt)
{
mid = (lt + rt)/2;
ql = mid;
qr = q;
pair < long long, long long > ansmin = query_min(1, 0, q);
pair < long long, long long > ansmax = query_max(1, 0, q);
if(ansmax.first - ansmin.first >= ro[i])
{
ans = mid;
lt = mid + 1;
}
else rt = mid - 1;
}
if(ans == -1)
{
long long val = suff[0];
s.pb(val);
continue;
}
long long val = 0;
if(ans != -1)
{
if(a[ans] > 0)val = ro[i];
}
ql = ans;
qr = q;
long long posmin = query_min(1, 0, q).second;
long long posmax = query_max(1, 0, q).second;
if(v[ans] > 0)val = ro[i];
else val = 0;
if(val)val += suff[posmin+1];
else val += suff[posmax+1];
val = min(val, 1LL *ro[i]);
val = max(val, 1LL * 0);
s.pb(val);
}
return s;
}
