#include "candies.h"
#include <algorithm>
#include <iostream>
#include <vector>
using ll = long long;
const int INF = int(1e9) + 1;
const int N = 1 << 18, SZ = N << 1;
ll sum[SZ], minv[SZ], maxv[SZ];
void change(int o, int l, int r, int k, int v) {
if (l == r) {
sum[o] = v;
minv[o] = std::min(v, 0);
maxv[o] = std::max(v, 0);
return;
}
int mid = (l + r) / 2;
if (k <= mid) change(o << 1, l, mid, k, v);
else change(o << 1 | 1, mid + 1, r, k, v);
sum[o] = sum[o << 1] + sum[o << 1 | 1];
minv[o] = std::min(minv[o << 1], sum[o << 1] + minv[o << 1 | 1]);
maxv[o] = std::max(maxv[o << 1], sum[o << 1] + maxv[o << 1 | 1]);
}
std::vector<std::pair<int, int>> modify[N];
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(), m = l.size();
for (int i = 0; i != m; ++i) {
modify[l[i]].emplace_back(i + 2, v[i]);
modify[r[i] + 1].emplace_back(i + 2, 0);
}
m += 1;
change(1, 0, m, 0, INF);
change(1, 0, m, 1, -INF);
std::vector<int> ans(n);
for (int i = 0; i != n; ++i) {
for (const auto& [k, v] : modify[i])
change(1, 0, m, k, v);
ll vl = sum[1], vr = sum[1], s = 0;
int o = 1, l = 0, r = m;
while (l != r) {
int mid = (l + r) / 2;
ll nl = std::min(vl, s + sum[o << 1] + minv[o << 1 | 1]),
nr = std::max(vr, s + sum[o << 1] + maxv[o << 1 | 1]);
if (nr - nl > c[i]) {
s += sum[o << 1];
o = o << 1 | 1;
l = mid + 1;
} else {
vl = nl;
vr = nr;
o = o << 1;
r = mid;
}
}
if (s <= vl)
ans[i] = c[i] - (vr - sum[1]);
else
ans[i] = sum[1] - vl;
}
return ans;
}
