#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int INF_int = 1 << 30;
int N, Q;
vi C, L, R, V;
vector<int> ans;
struct segtree
{
int size;
vi sum;
vi maxi;
vi mini;
const int offset = 2;
void compute(int x)
{
assert(x < size);
sum[x] = sum[2 * x] + sum[2 * x + 1];
mini[x] = min(mini[2 * x] + sum[2 * x + 1], mini[2 * x + 1]);
maxi[x] = max(maxi[2 * x] + sum[2 * x + 1], maxi[2 * x + 1]);
}
void init(int _size)
{
size = 1;
while (size < _size + offset + 1)
size *= 2;
sum.assign(2 * size, 0);
maxi.assign(2 * size, 0);
mini.assign(2 * size, 0);
sum[size] = mini[size] = maxi[size] = -INF_int;
sum[size + 1] = mini[size + 1] = maxi[size + 1] = INF_int;
for (int i = size - 1; i > 0; --i)
compute(i);
}
void add(int i, ll v)
{
add(i + offset, v, 1, 0, size);
}
void add(int i, ll v, int x, int lx, int rx)
{
if (rx - lx == 1)
{
sum[x] += -v;
mini[x] = sum[x];
maxi[x] = sum[x];
return;
}
int m = (lx + rx) / 2;
if (i < m)
add(i, v, 2 * x, lx, m);
else
add(i, v, 2 * x + 1, m, rx);
compute(x);
}
ll answer(ll capa)
{
// way up
ll ma = 0, mi = 0, su = 0;
int x = 2 * size - 1;
while (max(0LL, maxi[x]) - min(0LL, mini[x]) < capa)
{
ma = max(0LL, maxi[x]);
mi = min(0LL, mini[x]);
su = sum[x];
x /= 2;
}
// waydown
x = 2 * x;
while (x < size)
{
if (max(maxi[2 * x + 1] + su, ma) - min(mini[2 * x + 1] + su, mi) < capa)
{
ma = max(maxi[2 * x + 1] + su, ma);
mi = min(mini[2 * x + 1] + su, mi);
su = su + sum[2 * x + 1];
x = 2 * x;
}
else
x = 2 * x + 1;
}
mi = min(mi, mini[x] + su);
ma = max(ma, maxi[x] + su);
su += sum[x];
// calculation
if (sum[x] > 0)
return min(0 - mi, capa);
else if (sum[x] < 0)
return max(0LL, 0 - (ma - capa));
else
assert(false);
}
};
segtree seg;
std::vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v)
{
N = sz(_c), Q = sz(_l);
vpii Qu(Q); // {left, idx}
for (int i = 0; i < Q; ++i)
Qu[i] = {_l[i], i};
sort(all(Qu));
reverse(all(Qu));
seg.init(Q);
ans.resize(N);
priority_queue<pii, vpii, greater<pii>> q;
for (int i = 0; i < N; ++i)
{
while (!Qu.empty() && get<0>(Qu.back()) <= i)
{
int l, idx;
tie(l, idx) = Qu.back();
Qu.pop_back();
seg.add(idx, _v[idx]);
q.push({_r[idx], idx});
}
ans[i] = seg.answer(_c[i]);
while (!q.empty() && q.top().first <= i)
{
int r, idx;
tie(r, idx) = q.top();
q.pop();
seg.add(idx, -_v[idx]);
}
}
return ans;
}
