#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll inf = 1e18;
int n, q;
vector < int > s;
ll pref[maxn], cap[maxn];
vector < int > add[maxn], rem[maxn];
ll tree[4 * maxn], lazy[4 * maxn];
bool check(int pos, ll val)
{
ll min_height = inf;
ll max_height = -inf;
for (int i = pos; i < q + 2; i ++)
{
min_height = min(min_height, pref[i]);
max_height = max(max_height, pref[i]);
}
return (max_height - val > min_height);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v)
{
n = c.size();
q = l.size();
s.resize(n, 0);
for (int i = 0; i < n; i ++)
cap[i] = c[i];
for (int i = 0; i < q; i ++)
{
add[l[i]].push_back(i);
rem[r[i]].push_back(i);
}
for (int i = 0; i < n; i ++)
{
pref[0] = inf;
pref[1] = 0;
for (int j = 0; j < q; j ++)
{
pref[j + 2] = pref[j + 1];
if (l[j] <= i && r[j] >= i)
{
///cout << "here" << endl;
pref[j + 2] += v[j];
}
}
/**for (int j = 0; j < q + 2; j ++)
cout << pref[j] << " ";
cout << endl;*/
int lf = 1, rf = q + 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (check(mf, c[i]))
lf = mf + 1;
else
rf = mf - 1;
}
ll min_height = inf;
ll max_height = -inf;
for (int i = rf; i < q + 2; i ++)
{
min_height = min(min_height, pref[i]);
max_height = max(max_height, pref[i]);
}
if (max_height == pref[rf])
s[i] = pref[q + 1] - min_height;
else
s[i] = pref[q + 1] - (max_height - c[i]);
}
return s;
}
