#include "candies.h"
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef struct {
int l;
int r;
ll sum;
ll min_sum;
ll max_sum;
} Node;
typedef struct {
int id;
int pos;
int val;
} Query;
Node tree[800007];
Query query[400007];
bool operator <(const Query a, const Query b){
return a.pos < b.pos;
}
void build(int x, int l, int r){
tree[x].l = l;
tree[x].r = r;
if (l == r) return;
int mid = (l + r) >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
}
inline void update(int x){
int ls = x * 2, rs = x * 2 + 1;
tree[x].sum = tree[ls].sum + tree[rs].sum;
tree[x].min_sum = min(tree[ls].min_sum, tree[rs].min_sum + tree[ls].sum);
tree[x].max_sum = max(tree[ls].max_sum, tree[rs].max_sum + tree[ls].sum);
}
void add(int x, int pos, int val){
if (tree[x].l == tree[x].r){
tree[x].sum += val;
tree[x].min_sum = min(tree[x].sum, 0ll);
tree[x].max_sum = max(tree[x].sum, 0ll);
return;
}
if (pos <= ((tree[x].l + tree[x].r) >> 1)){
add(x * 2, pos, val);
} else {
add(x * 2 + 1, pos, val);
}
update(x);
}
ll do_query(int x, int k, ll cur_sum, ll cur_min_sum, ll cur_max_sum){
if (tree[x].l == tree[x].r) return (tree[x].sum <= 0 && cur_max_sum > k) || (tree[x].sum > 0 && cur_min_sum >= -k) ? k + cur_sum - cur_max_sum : cur_sum - cur_min_sum;
int rs = x * 2 + 1;
ll y = min(tree[rs].min_sum, cur_min_sum + tree[rs].sum), z = max(tree[rs].max_sum, cur_max_sum + tree[rs].sum);
if (z - y > k) return do_query(rs, k, cur_sum, cur_min_sum, cur_max_sum);
return do_query(x * 2, k, cur_sum + tree[rs].sum, y, z);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
int n = c.size(), q = l.size(), m = 0;
vector<int> ans;
c.insert(c.begin(), 0);
l.insert(l.begin(), 0);
r.insert(r.begin(), 0);
v.insert(v.begin(), 0);
build(1, 0, q);
for (register int i = 1; i <= q; i++){
m++;
query[m].id = i;
query[m].pos = ++l[i];
query[m].val = v[i];
if (++r[i] < n){
m++;
query[m].id = i;
query[m].pos = r[i] + 1;
query[m].val = -v[i];
}
}
sort(query + 1, query + m + 1);
for (register int i = 1, j = 1; i <= n; i++){
while (j <= m && query[j].pos == i){
add(1, query[j].id, query[j].val);
j++;
}
ans.push_back(do_query(1, c[i], 0, 0, 0));
}
return ans;
}
