#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
ll CAP;
struct Node {
ll min_val, max_val, pre_min, pre_max, sum;
Node operator+(const Node &other) {
const auto apply = [&](const ll v) {
if (v + other.pre_min < 0)
return other.min_val;
if (v + other.pre_max > CAP)
return other.max_val;
return v + other.sum;
};
return {apply(min_val), apply(max_val), min(pre_min, sum + other.pre_min), max(pre_max, sum + other.pre_max), sum + other.sum};
}
};
struct ST {
const int N;
vt<Node> st;
ST(const int n) : N(n), st(n << 1, {0, CAP, 0, 0, 0}) {}
void update(int i, const ll v) {
st[i += N] = {min(CAP, max(v, 0ll)), max(0ll, CAP + min(v, 0ll)), min(v, 0ll), max(v, 0ll), v};
while (i >>= 1)
st[i] = st[i<<1] + st[i<<1|1];
};
Node query(int l, int r) {
Node lft = {0, CAP, 0, 0, 0};
Node rht = {0, CAP, 0, 0, 0};
for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
lft = lft + st[l++];
if (r & 1)
rht = st[--r] + rht;
}
return lft + rht;
}
};
vt<int> distribute_candies(vt<int> C, vt<int> L, vt<int> R, vt<int> V) {
const int N = size(C), Q = size(L);
if (*max_element(all(L)) == 0 && *min_element(all(R)) == N-1) {
vt<ll> psum(Q+1);
FOR(i, 0, Q-1)
psum[i+1] = psum[i] + V[i];
vt<ll> smax = psum, smin = psum;
ROF(i, Q-1, 0) {
smax[i] = max(smax[i+1], smax[i]);
smin[i] = min(smin[i+1], smin[i]);
}
vt<int> ret(N);
FOR(i, 0, N-1) {
if (smax[0] - smin[0] <= C[i]) {
ret[i] = psum[Q] - smin[0];
} else {
int lo = 0, hi = Q;
while (lo < hi) {
const int mid = lo + hi + 1 >> 1;
if (smax[mid] - smin[mid] > C[i])
lo = mid;
else
hi = mid - 1;
}
ret[i] = (psum[lo] < psum[Q] ? C[i] - (smax[lo] - psum[Q]) : psum[Q] - smin[lo]);
}
}
return ret;
}
if (*min_element(all(C)) == *max_element(all(C))) {
CAP = C[0];
vt<vt<int>> ins(N), rem(N);
FOR(i, 0, Q-1) {
ins[L[i]].push_back(i);
rem[R[i]].push_back(i);
}
ST st(Q);
vt<int> ret(N);
FOR(i, 0, N-1) {
for (const auto &j : ins[i])
st.update(j, V[j]);
ret[i] = st.query(0, Q-1).min_val;
for (const auto &j : rem[i])
st.update(j, 0);
}
return ret;
}
if (max(N, Q) <= 2000) {
vt<int> ans(N);
FOR(i, 0, N-1)
FOR(j, 0, Q-1)
if (L[j] <= i && i <= R[j]) {
ans[i] += V[j];
ans[i] = min(ans[i], C[i]);
ans[i] = max(ans[i], 0);
}
return ans;
}
if (*min_element(all(V)) > 0) {
vt<ll> psum(N);
FOR(i, 0, Q-1) {
psum[L[i]] += V[i];
if (R[i] + 1 < N)
psum[R[i] + 1] -= V[i];
}
FOR(i, 0, N-1) {
if (i)
psum[i] += psum[i-1];
C[i] = min((ll)C[i], psum[i]);
}
return C;
}
}
