#include "candies.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1 << 18;
struct node
{
ll pfmin, pfmax, sum;
bool up;
void init(int val)
{
up = (val >= 0);
pfmin = min(0, val), pfmax = max(0, val), sum = val;
}
void merge(node a, node b)
{
up = a.up;
pfmin = min(a.pfmin, a.sum + b.pfmin);
pfmax = max(a.pfmax, a.sum + b.pfmax);
sum = a.sum + b.sum;
}
};
vector<node> st(2*maxn);
void update(int i, int val)
{
st[i += maxn].init(val);
for (i = (i >> 1); i > 0; i >>= 1) st[i].merge(st[i<<1], st[(i<<1)|1]);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
vector<int> ans(n);
update(0, -*max_element(c.begin(), c.end()));
vector<vector<int> > u(n+1);
for (int i = 0; i < q; i++)
{
u[l[i]].push_back(i);
u[r[i]+1].push_back(i);
}
for (int i = 0; i < n; i++)
{
for (int id : u[i])
{
if (l[id] == i) update(id+1, v[id]);
else update(id+1, 0);
}
node suf; suf.init(0);
int vr = 1;
while (vr < maxn)
{
vr = (vr << 1) | 1; // pravy syn
node nw; nw.merge(st[vr], suf);
if (nw.pfmax - nw.pfmin < c[i]) // posunieme sa o krok dolava
suf = nw, vr--;
}
suf.merge(st[vr], suf); // urobime to trosku vacsie ako c[i]
if (suf.up) // ideme nahor, vyska od hornej steny je ok
ans[i] = (ll)c[i] - (suf.pfmax - suf.sum);
else // ideme nadol, vyska od dolnej steny je ok
ans[i] = suf.sum - suf.pfmin;
}
return ans;
}
