#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int sum;
int lmin, lmax;
int umin, umax;
Node() : sum(0), lmin(INT_MAX), lmax(INT_MIN), umin(INT_MAX), umax(INT_MIN) {}
Node(int val, int cap) : sum(val), lmin(val), lmax(val), umin(cap - val), umax(cap - val) {}
Node(const Node& A, const Node& B) {
sum = A.sum + B.sum;
lmin = min(A.lmin, A.lmin < INT_MAX ? B.lmin : INT_MAX);
lmax = max(A.lmax, B.lmax);
umin = min(A.umin, A.umin < INT_MAX ? B.umin : INT_MAX);
umax = max(A.umax, B.umax);
}
};
struct SegmentTree {
int n; vector<int> arr, cap;
vector<Node> st;
vector<int> lazy;
SegmentTree(int N, vector<int> &Cap) {
n = N;
cap = Cap;
arr.assign(n, 0);
st.assign(4*n, Node());
lazy.assign(4*n, 0);
build(0, 0, n);
}
Node build(int i, int l, int r) {
if (l + 1 == r) return st[i] = Node(0, cap[l]);
int m = l + (r - l) / 2;
return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
}
void apply_update(int i, int l, int r, int op) {
int length = r - l;
lazy[i] += op;
st[i].sum += op * length;
st[i].lmin += op;
st[i].lmax += op;
st[i].umin -= op;
st[i].umax -= op;
}
void push_down(int i, int l, int r) {
int m = l + (r - l) / 2;
apply_update(2 * i + 1, l, m, lazy[i]);
apply_update(2 * i + 2, m, r, lazy[i]);
lazy[i] = 0;
}
Node query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return Node();
if (ql <= l && r <= qr) return st[i];
push_down(i, l, r);
int m = l + (r - l) / 2;
return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
Node upd_increase(int i, int l, int r, int ql, int qr, int qdelt) {
if (qr <= l || r <= ql) return st[i];
if (st[i].umax <= 0) return st[i];
if (ql <= l && r <= qr && st[i].umin - qdelt >= 0) {
apply_update(i, l, r, qdelt);
return st[i];
}
if (l + 1 == r) {
int nv = min(st[i].sum + qdelt, cap[l]);
return st[i] = Node(nv, cap[l]);
}
push_down(i, l, r);
int m = l + (r - l) / 2;
return st[i] = Node(upd_increase(2*i+1, l, m, ql, qr, qdelt), upd_increase(2*i+2, m, r, ql, qr, qdelt));
}
Node upd_decrease(int i, int l, int r, int ql, int qr, int qdelt) {
if (qr <= l || r <= ql) return st[i];
if (st[i].lmax <= 0) return st[i];
if (ql <= l && r <= qr && st[i].lmin + qdelt >= 0) {
apply_update(i, l, r, qdelt);
return st[i];
}
if (l + 1 == r) {
int nv = max(st[i].sum + qdelt, 0);
return st[i] = Node(nv, cap[l]);
}
push_down(i, l, r);
int m = l + (r - l) / 2;
return st[i] = Node(upd_decrease(2*i+1, l, m, ql, qr, qdelt), upd_decrease(2*i+2, m, r, ql, qr, qdelt));
}
void update(int l, int r, int delta) {
if (delta < 0) upd_decrease(0, 0, n, l, r, delta);
else upd_increase(0, 0, n, l, r, delta);
}
int query(int k) {
return query(0, 0, n, k,k+1).sum;
}
};
struct slow {
int n; vector<int> cap, arr;
slow(int N, vector<int> &cp) {
n = N;
cap = cp;
arr.assign(n, 0);
}
void upd_increase(int l, int r, int delt) {
for (int i = l; i <= r; i++) {
arr[i] = min(arr[i] + delt, cap[i]);
}
}
void upd_decrease(int l, int r, int delt) {
for (int i = l; i <= r; i++) {
arr[i] = max(arr[i] + delt, 0);
}
}
void update(int l, int r, int delt) {
if (delt < 0) upd_decrease(l, r, delt);
else upd_increase(l, r, delt);
}
int query(int k) {
return arr[k];
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = v.size();
vector<int> s(n);
auto st = SegmentTree(n, c);
// auto sl = slow(n, c);
for (int i = 0; i < q; i++) {
st.update(l[i], r[i]+1, v[i]);
// sl.update(l[i], r[i], v[i]);
}
for (int i = 0; i < n; i++) {
s[i] = st.query(i);
// cout << st.query(i) << " ";
}
// cout << "\n";
// for (int i = 0; i < n; i++) {
// cout << sl.query(i) << " ";
// }
// cout << "\n";
// s = sl.arr;
return s;
}
