#include <bits/stdc++.h>
#include "candies.h"
#define pb push_back
#define f first
#define s second
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll oo = 1e18;
const ld eps = (ld)1 / oo;
const ll N = 2e5 + 100;
const ll M = 1e6;
struct tree
{
tree *L = NULL;
tree *R = NULL;
int l;
int r;
int mdl;
ll lb = 0;
ll mn = 0;
ll mx = 0;
tree (int _l, int _r) : l(_l), r(_r)
{
mdl = (l + r) >> 1;
if (l == r) return;
L = new tree(l, mdl);
R = new tree(mdl + 1, r);
}
void push()
{
if (lb != 0)
{
mx += lb;
mn += lb;
if (l != r)
{
L -> lb += lb;
R -> lb += lb;
}
lb = 0;
}
}
void upd(int _l, int _r, int _vl)
{
push();
if (_l > _r) return ;
if (_l == l && _r == r)
{
lb += _vl;
push();
return;
}
L -> upd(_l, min(mdl, _r), _vl);
R -> upd(max(mdl + 1, _l), _r, _vl);
mn = min(L -> mn, R -> mn);
mx = max(L -> mx, R -> mx);
}
ll calc_mx(int _l, int _r)
{
push();
if (_l > _r) return -oo;
if (_l == l && _r == r) return mx;
return max(L -> calc_mx(_l, min(mdl, _r)), R -> calc_mx(max(mdl + 1, _l), _r));
}
ll calc_mn(int _l, int _r)
{
push();
if (_l > _r) return oo;
if (_l == l && _r == r) return mn;
return min(L -> calc_mn(_l, min(mdl, _r)), R -> calc_mn(max(mdl + 1, _l), _r));
}
};
std::vector<int> distribute_candies (std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
int q = l.size();
vector <pair<int, int> > event[n + 1];
for (int i = 0; i < q; i++)
{
event[l[i]].pb({i + 1, v[i]});
event[r[i] + 1].pb({i + 1, -v[i]});
}
tree *root = new tree(0, q);
vector <int> ans(n);
for (int i = 0; i < n; i++)
{
for (auto j : event[i]) root -> upd(j.f, q, j.s);
int l = 0, r = q;
while (l < r)
{
int mdl = (l + r + 1) >> 1;
if (root -> calc_mx(mdl, q) - root -> calc_mn(mdl, q) < c[i]) r = mdl - 1;
else l = mdl;
}
ll mx = root -> calc_mx(l, q);
ll mn = root -> calc_mn(l, q);
if (mx - mn <= c[i])
{
ans[i] = root -> calc_mx(q, q) - mn;
continue;
}
else
{
ll mx1 = root -> calc_mx(l + 1, q);
ll mn1 = root -> calc_mn(l + 1, q);
if (mn < mn1) mn1 = mx1 - c[i];
ans[i] = root -> calc_mx(q, q) - mn1;
}
}
return ans;
}
//int main()
//{
// int n;
// cin >> n;
// vector <int> a(n);
// for (int i = 0; i < n; i++) cin >> a[i];
// int q;
// cin >> q;
// vector <int> l(q), r(q), v(q);
// for (int i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];
// vector <int> ans = distribute_candies(a, l, r, v);
// for (auto i : ans) cout << i << " ";
//}
