#include "candies.h"
#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
int n, q;
ll mx[1 << 19], mn[1 << 19], add[1 << 19];
void lazy(int i) {
mn[i + i] += add[i];
mn[i + i + 1] += add[i];
mx[i + i] += add[i];
mx[i + i + 1] += add[i];
add[i + i] += add[i];
add[i + i + 1] += add[i];
add[i] = 0;
}
void update(int i, int s, int e, int x, int v) {
if (e < x) return;
if (x <= s) {
mn[i] += v;
mx[i] += v;
add[i] += v;
return;
}
lazy(i);
int m = (s + e) / 2;
update(i + i, s, m, x, v);
update(i + i + 1, m + 1, e, x, v);
mn[i] = min(mn[i + i], mn[i + i + 1]);
mx[i] = max(mx[i + i], mx[i + i + 1]);
}
ll low, high;
int find(int i, int s, int e, ll low, ll high, int c) {
if (max(high, mx[i]) - min(low, mn[i]) <= c) return -1;
if (s == e) {
::low = min(low, mn[i]);
::high = max(high, mx[i]);
return s;
}
lazy(i);
int m = (s + e) / 2;
int r = find(i + i + 1, m + 1, e, low, high, c);
if (r != -1) return r;
return find(i + i, s, m, min(low, mn[i + i + 1]), max(high, mx[i + i + 1]), c);
}
ll get(int i, int s, int e, int x) {
if (s == e) return add[i];
lazy(i);
int m = (s + e) / 2;
if (x <= m) return get(i + i, s, m, x);
else return get(i + i + 1, m + 1, e, x);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size();
l.insert(l.begin(), 0);
l.insert(l.begin(), 0);
r.insert(r.begin(), n - 1);
r.insert(r.begin(), n - 1);
v.insert(v.begin(), 0);
v.insert(v.begin(), 0);
q = v.size();
vector<vector<int>> A(n, vector<int>({ 0, 1 })), R(n, vector<int>({ 0, 1 }));
for (int i = 2; i < q; ++i) {
A[l[i]].push_back(i);
R[r[i]].push_back(i);
}
vector<int> ans;
for (int i = 0; i < n; ++i) {
v[0] = c[i];
v[1] = -c[i];
for (int j : A[i]) update(1, 0, q, j + 1, v[j]);
int x = find(1, 0, q, 1e18, -1e18, c[i]);
if (x == -1) ans.push_back(get(1, 0, q, q));
else {
ll p = get(1, 0, q, x);
if (p == low) ans.push_back(c[i] + get(1, 0, q, q) - high);
else ans.push_back(get(1, 0, q, q) - low);
}
for (int j : R[i]) update(1, 0, q, j + 1, -v[j]);
}
return ans;
}
