#include "candies.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;
int n, q;
struct query {
int type, val, timer;
query() {}
query(int _type, int _val, int _timer) : type(_type), val(_val), timer(_timer) {}
};
vector<query> events[maxn];
int64_t stSum[4*maxn], lz[4*maxn];
li stMin[4*maxn], stMax[4*maxn];
void apple(int r, int d) {
stSum[r] += d;
stMin[r].fi += d;
stMax[r].fi += d;
lz[r] += d;
}
void down(int r) {
if (lz[r]) {
apple(r<<1, lz[r]);
apple(r<<1|1,lz[r]);
lz[r] = 0;
}
}
void up(int r) {
stSum[r] = stSum[r<<1] + stSum[r<<1|1];
stMin[r] = (stMin[r<<1].fi <= stMin[r<<1|1].fi ? stMin[r<<1] : stMin[r<<1|1]);
stMax[r] = (stMax[r<<1].fi >= stMax[r<<1|1].fi ? stMax[r<<1] : stMax[r<<1|1]);
}
void build(int r = 1, int lo = -2, int hi = q-1) {
if (lo == hi) {
stMin[r] = stMax[r] = {0, lo};
stSum[r] = 0;
return;
}
int mid = (lo + hi) >> 1;
build(r<<1, lo, mid);
build(r<<1|1, mid+1, hi);
up(r);
}
void update(int u, int v, int d, int r = 1, int lo = -2, int hi = q-1) {
if (u <= lo && hi <= v) {
apple(r, d);
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update(u, v, d, r<<1, lo, mid);
if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
up(r);
}
li getMin(int u, int v, int r = 1, int lo = -2, int hi = q-1) {
if (u <= lo && hi <= v) return stMin[r];
down(r);
int mid = (lo + hi) >> 1;
return min((u <= mid ? getMin(u, v, r<<1, lo, mid) : li{LLONG_MAX, 0}), (v > mid ? getMin(u, v, r<<1|1, mid+1, hi) : li{LLONG_MAX, 0}));
}
li getMax(int u, int v, int r = 1, int lo = -2, int hi = q-1) {
if (u <= lo && hi <= v) return stMax[r];
down(r);
int mid = (lo + hi) >> 1;
li A = (u <= mid ? getMax(u, v, r<<1, lo, mid) : li{LLONG_MIN, 0}), B = (v > mid ? getMax(u, v, r<<1|1, mid+1, hi) : li{LLONG_MIN, 0});
return (A.fi >= B.fi ? A : B);
}
int64_t getSum(int u, int v, int r = 1, int lo = -2, int hi = q-1) {
if (u <= lo && hi <= v) return stSum[r];
down(r);
int mid = (lo + hi) >> 1;
return (u <= mid ? getSum(u, v, r<<1, lo, mid) : 0) +
(v > mid ? getSum(u, v, r<<1|1,mid+1,hi): 0);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size(); q = l.size();
events[0].emplace_back(1, 1e9, -2);
events[0].emplace_back(1, -1e9, -1);
for (int i = 0; i < q; i++) {
events[l[i]].emplace_back(1, v[i], i);
events[r[i]+1].emplace_back(-1, v[i], i);
}
build();
vector<int> ans;
for (int o = 0; o < n; o++) {
for (auto [type, val, timer] : events[o])
update(timer, q-1, type*val);
int lo = -3, hi = q-1;
while (hi-lo>1) {
int mid = (lo + hi) >> 1;
li A = getMax(mid, q-1), B = getMin(mid, q-1);
if (max(A.fi-B.fi, B.fi-A.fi) <= c[o]) hi = mid;
else lo = mid;
}
if (1) {
li p = getMax(hi, q-1);
if ((p.se == -2 || v[p.se] > 0) && p.fi - getMin(p.se, q-1).fi <= c[o]) {
ans.emplace_back(c[o] + getSum(q-1, q-1) - getSum(p.se, p.se));
continue;
}
}
li p = getMin(hi, q-1);
ans.emplace_back(getSum(q-1, q-1) - getSum(p.se, p.se));
}
return ans;
}
