#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int sum;
int mn, mx;
Node() : sum(0), mn(INT_MAX), mx(INT_MIN) {};
Node(int s, int MN, int MX) : sum(s), mn(MN), mx(MX) {};
Node(int v) : sum(v), mn(v), mx(v) {};
Node(Node left, Node right) {
sum = left.sum + right.sum;
mn = min(left.mn, right.mn);
mx = max(left.mx, right.mx);
}
};
struct SegmentTree {
int n, cap; vector<int> arr;
vector<Node> st;
vector<int> lazy;
SegmentTree(int N, int Cap) {
n = N;
cap = Cap;
arr.assign(n, 0);
st.assign(4*n, Node(0));
lazy.assign(4*n, 0);
}
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].mx += op;
st[i].mn += 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].mn >= cap) return st[i];
if (ql <= l && r <= qr && st[i].mx + qdelt <= cap) {
apply_update(i, l, r, qdelt);
return st[i];
}
if (l + 1 == r) {
int nv = min(st[i].sum + qdelt, cap);
return st[i] = Node(nv);
}
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].mx <= 0) return st[i];
if (ql <= l && r <= qr && st[i].mn + 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);
}
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[0]);
// 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;
}
