/*
We have an array x[] of length n.
Define x[0] = 0, x[i+1] = clamp(x[i] + v[i], [0, c])
Now, the goal is to find x[n], but this is hard.
So, define p[0] = 0, p[i+1] = p[i] + v[i], that is, the prefix sum.
Now, define d[i] = x[i] - p[i], that is, x[i] = p[i] + d[i]. We will try to find d[i] instead.
How does d[i] move? Imagine a window of length `c` around the current value.
If the value exceeds the upper bound of the window, the whole window moves upwards and d[i] decreases.
Similarly, if the value goes below the lower bound, d[i] increases.
We know that 0 <= x[i] <= c. Hence, 0 <= p[i] + d[i] <= c
-p[i] <= d[i] <= c-p[i]
Basically, if d[i] were to go below -p[i] or above c-p[i], it'd be clamped back in range.
Notice that a necessary (but not sufficient) condition to detect that clamps occur after i is
max(p[j]) - min(p[j]) >= c for j >= i. Let us find the first index `i` such that max(p[j]) - min(p[j]) < c.
Then, we claim that either:
- d[i] <= d[i+1] <= d[i+2] <= ... <= d[n]
or - d[i] >= d[i+1] >= d[i+2] >= ... >= d[n]
In simpler words, we only ever clamp downwards, or upwards. This is true, because if we clamped downwards and then upwards (or vice versa), we would have to
travel a distance >= c to go from 0 to c or c to 0.
If i==0, then we know that we start at 0 and never go further than c. Hence, all clamping must be upward. Also, we know that the last
clamp occurs at the min element, hence d[n] = -min(p[j]).
Otherwise, i != 0. Then we look at x[i-1]. We know that 0 <= x[i-1] <= c, -d[i-1] <= p[i-1] <= c-d[i-1].
We also know that including i-1 will make max(p[j]) - min(p[j]) >= c, hence p[i-1] is either a new min or max element
If p[i-1] is the new min element, then max(p[j]) - p[i-1] >= c, so c - max(p[j]) <= -p[i-1].
We know that 0 <= x[i-1] and x[i-1] = p[i-1] + d[i-1], so 0 <= p[i-1] + d[i-1], -p[i-1] <= d[i-1]
Hence d[i-1] >= c - max(p[j]), so d gets clamped down, and d[n] = c - max(p[j]). d will not get clamped up since c - max(p[j]) >= -min(p[j]).
If p[i-1] is the new max element, then p[i-1] - min(p[j]) >= c => c + min(p[j]) <= p[i-1]
We know that x[i-1] <= c, so p[i-1] + d[i-1] <= c, p[i-1] <= c-d[i-1]
Hence d[i-1] <= -min(p[j]), so d gets clamped up, and d[n] = -min(p[j]). d will not get clamped down since -min(p[j]) <= c - max(p[j]).
*/
#include <bits/stdc++.h>
using namespace std;
namespace {
using int64 = long long;
const int64 inf = 1e15;
class lazy_segment_tree {
int n;
vector<int64> segmin, segmax, lazy;
void push(int v) {
segmin[v] += lazy[v], segmax[v] += lazy[v];
if (v < 2 * n) {
lazy[2 * v] += lazy[v], lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
void pull(int v) { segmin[v] = std::min(segmin[2 * v], segmin[2 * v + 1]), segmax[v] = std::max(segmax[2 * v], segmax[2 * v + 1]); }
void add(int v, int tl, int tr, int l, int r, int64 del) {
push(v);
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] += del;
push(v);
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, del), add(2 * v + 1, tm + 1, tr, l, r, del);
pull(v);
}
pair<int64, int64> query(int v, int tl, int tr, int l, int r) {
push(v);
if (tr < l || r < tl) {
return {inf, -inf};
}
if (l <= tl && tr <= r) {
return {segmin[v], segmax[v]};
}
int tm = (tl + tr) / 2;
auto [lm, lM] = query(2 * v, tl, tm, l, r);
auto [rm, rM] = query(2 * v + 1, tm + 1, tr, l, r);
return {std::min(lm, rm), std::max(lM, rM)};
}
public:
lazy_segment_tree(int n) : n(n), segmin(4 * n), segmax(4 * n), lazy(4 * n) {}
void add(int l, int r, int64 del) { add(1, 0, n - 1, l, r, del); }
int64 min(int l, int r) { return query(1, 0, n - 1, l, r).first; }
int64 max(int l, int r) { return query(1, 0, n - 1, l, r).second; }
int64 at(int i) { return min(i, i); }
};
} // namespace
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
const int n = c.size(), q = v.size();
vector<vector<int>> add(n), rem(n + 1);
for (int i = 0; i < q; ++i) {
add[l[i]].push_back(i);
rem[r[i] + 1].push_back(i);
}
lazy_segment_tree st(q + 1);
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
for (int &j : add[i]) {
st.add(j + 1, q, v[j]);
}
for (int &j : rem[i]) {
st.add(j + 1, q, -v[j]);
}
int ii = *ranges::partition_point(views::iota(0, q), [&](int ii) { return st.max(ii, q) - st.min(ii, q) >= c[i]; });
if (ii == 0) {
ans[i] = st.at(q) - st.min(ii, q);
continue;
}
if (st.at(ii - 1) < st.min(ii, q)) {
ans[i] = st.at(q) + c[i] - st.max(ii, q);
} else {
ans[i] = st.at(q) - st.min(ii, q);
}
}
return ans;
}
