#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "candies.h"
struct info {
ll mi, mx, laz;
const info operator+(const info &o) const {
return {min(mi, o.mi), max(mx, o.mx), 0};
}
void tag(ll dt) {
laz += dt;
mi += dt;
mx += dt;
}
} segt[200005 << 2];
void pd(int idx, int l, int r) {
if (r - l == 1)
return;
segt[idx * 2].tag(segt[idx].laz);
segt[idx * 2 + 1].tag(segt[idx].laz);
segt[idx].laz = 0;
}
void ad(int idx, int l, int r, int L, int R, int v) {
if (L <= l && r <= R)
return segt[idx].tag(v);
if (R <= l || r <= L)
return;
pd(idx, l, r);
ad(idx * 2, l, (l + r) / 2, L, R, v);
ad(idx * 2 + 1, (l + r) / 2, r, L, R, v);
segt[idx] = segt[idx * 2] + segt[idx * 2 + 1];
}
int fin(int idx, int l, int r, ll sfxmin, ll sfxmax, int cap, ll tot) {
if (r - l == 1) {
sfxmin = min(sfxmin, segt[idx].mi);
sfxmax = max(sfxmax, segt[idx].mx);
// cout << cap << ' ' << sfxmin << ' ' << sfxmax << ' ' << l << endl;
if (sfxmin == segt[idx].mi)
return tot - (sfxmax - cap);
return tot - sfxmin;
}
pd(idx, l, r);
ll nmin = min(sfxmin, segt[idx * 2 + 1].mi);
ll nmax = max(sfxmax, segt[idx * 2 + 1].mx);
if (nmax - nmin >= cap)
return fin(idx * 2 + 1, (l + r) / 2, r, sfxmin, sfxmax, cap, tot);
return fin(idx * 2, l, (l + r) / 2, nmin, nmax, cap, tot);
}
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<vector<pair<int, int>>> op(n + 1);
std::vector<int> s(n);
for (int i = 0; i < q; i++) {
op[l[i]].push_back({i, v[i]});
op[r[i] + 1].push_back({i, -v[i]});
}
ll tot = 0;
for (int i = 0; i < n; i++) {
for (auto [u, dt] : op[i]) {
tot += dt;
ad(1, 0, q + 1, u + 1, q + 1, dt);
}
// cout << segt[1].mx << ' ' << segt[1].mi << endl;
if (segt[1].mx - segt[1].mi > c[i])
s[i] = fin(1, 0, q + 1, 1e18, -1e18, c[i], tot);
else
s[i] = tot - segt[1].mi;
assert(0 <= s[i] && s[i] <= c[i]);
}
return s;
}
