#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), pmax(Q);
psum[0] = V[0];
pmax[0] = max(V[0], 0);
FOR(i, 1, Q-1) {
psum[i] = psum[i-1] + V[i];
pmax[i] = max(pmax[i-1], psum[i]);
}
vt<ll> smin(Q), smax(Q);
ll cur = LLONG_MIN;
CAP = LLONG_MAX;
ST st(Q);
ROF(i, Q-1, 0) {
st.update(i, V[i]);
cur = max(cur, psum[i]);
smin[i] = psum[i] - pmax[i];
smax[i] = cur - psum[i];
if (i + 1 < Q) {
smin[i] = min(smin[i], smin[i+1]);
smax[i] = max(smax[i], smax[i+1]);
}
}
#ifdef DEBUG
cout << "Bruh:\n";
FOR(i, 0, Q-1)
cout << psum[i] << "\n "[i+1<Q];
FOR(i, 0, Q-1)
cout << smin[i] << "\n "[i+1<Q];
FOR(i, 0, Q-1)
cout << smax[i] << "\n "[i+1<Q];
FOR(i, 0, Q-1)
cout << pmax[i] << "\n "[i+1<Q];
#endif
vt<int> ret(N);
FOR(i, 0, N-1) {
const int j = upper_bound(all(smin), -C[i]) - smin.begin() - 1;
ret[i] = st.query(j+1, Q-1).min_val - max(0ll, (j >= 0 ? smax[j] : cur) - C[i]);
}
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;
}
}
