#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree {
struct Node {
int val = 0;
int mn = 0;
int mx = 0;
int lazy = 0;
};
vector<Node> tree;
int n;
vector<int> limit;
segtree(int n, const vector<int>& c) : n(n), limit(c) {
tree.resize(4 * n);
}
void push(int node, int start, int end) {
if(tree[node].lazy != 0) {
tree[node].val += tree[node].lazy;
tree[node].mn += tree[node].lazy;
tree[node].mx += tree[node].lazy;
if(start != end) {
tree[2*node].lazy += tree[node].lazy;
tree[2*node+1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
if(start == end) {
tree[node].val = max(0, min(tree[node].val, limit[start]));
tree[node].mn = tree[node].val;
tree[node].mx = tree[node].val;
} else {
tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
}
}
void update(int node, int start, int end, int l, int r, int val) {
push(node, start, end);
if(start > r || end < l) return;
if(l <= start && end <= r) {
tree[node].lazy += val;
push(node, start, end);
if(tree[node].mn < 0 || tree[node].mx > limit[start]) {
if(start != end) {
push(2*node, start, (start+end) / 2);
push(2*node+1, (start+end) / 2 + 1, end);
}
}
return;
}
int mid = (start + end) / 2;
update(2*node, start, mid, l, r, val);
update(2*node+1, mid+1, end, l, r, val);
tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
}
int get(int node, int start, int end, int id) {
push(node, start, end);
if(start == end) return tree[node].val;
int mid = (start + end) / 2;
if(id <= mid) return get(2*node, start, mid, id);
else return get(2*node+1, mid+1, end, id);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
int sz = c.size();
segtree ST(sz, c);
for(int i = 0; i < v.size(); i++){
ST.update(1, 0, sz-1, l[i], r[i], v[i]);
}
vector<int> ans(sz);
for(int i = 0; i < sz; i++){
ans[i] = ST.get(1, 0, sz-1, i);
}
return ans;
}
