#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 10;
int n, q;
const int64_t INF = 1e15;
struct seg_node {
int64_t mn, mx;
int min_ind, max_ind;
seg_node() :mn(INF), mx(-INF) {}
seg_node(int64_t x, int id): mn(x), mx(x), min_ind(id), max_ind(id){}
inline int64_t dif() {return mx - mn;}
inline void apply(int64_t x) {
mn += x;
mx += x;
}
};
int64_t bit[nax];
void update(int idx, int64_t val) {
for (; idx <= q ; idx += idx & -idx) bit[idx] += val;
}
int64_t get_sum(int idx) {
int64_t res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
seg_node operator +(const seg_node &a, const seg_node &b) {
seg_node res;
res.min_ind = a.mn < b.mn ? (res.mn = a.mn, a.min_ind) : (res.mn = b.mn, b.min_ind);
res.max_ind = a.mx > b.mx ? (res.mx = a.mx, a.max_ind) : (res.mx = b.mx, b.max_ind);
return res;
}
seg_node sg[nax << 2];
int64_t tag[nax << 2];
void push(int v) {
if (!tag[v]) return;
sg[v << 1].apply(tag[v]);
sg[v << 1 | 1].apply(tag[v]);
tag[v << 1] += tag[v];
tag[v << 1 | 1] += tag[v];
tag[v] = 0;
}
void range_add(int v, int x, int y, int l, int r, int64_t add) {
if (x != y) push(v);
if (l == x && r == y) {
tag[v] += add;
sg[v].apply(add);
if (x != y) push(v);
return;
}
int mid = x + y >> 1;
if (r <= mid) range_add(v << 1, x, mid, l, r, add);
else if (l > mid) range_add(v * 2 + 1, mid + 1, y, l, r, add);
else range_add(v << 1, x, mid, l, mid, add), range_add(v * 2 + 1, mid + 1, y, mid + 1, r, add);
sg[v] = sg[v << 1] + sg[v << 1 | 1];
}
/// find maximum index such that
/// max(index, q) - min(index, q) >= k
int find_last(int v, int l, int r, int tar, seg_node &info) {
if (l == r) return (info + sg[v]).dif() >= tar ? l : -1;
push(v);
if ((info + sg[v]).dif() < tar) return -1;
int mid = l + r >> 1;
seg_node info_right = info + sg[v << 1 | 1];
if (info_right.dif() >= tar) return find_last(v << 1 | 1, mid + 1, r, tar, info);
info = info_right;
return find_last(v << 1, l, mid, tar, info);
}
void build(int v, int l, int r) {
if (l == r) {
sg[v] = seg_node(0, l);
} else {
int mid = l + r >> 1;
build(v << 1, l, mid);
build(v << 1 | 1, mid + 1, r);
sg[v] = sg[v << 1] + sg[v << 1 | 1];
}
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n = c.size();
q = v.size();
vector <vector <pair <int, int>>> sc(n + 1);
for (int i = 0 ; i < q ; ++ i) {
sc[l[i]].emplace_back(i + 1, v[i]);
sc[r[i] + 1].emplace_back(i + 1, -v[i]);
}
build(1, 0, q);
vector <int> ans(n);
int64_t all_sum = 0;
for (int s = 0 ; s < n ; ++ s) {
int k = c[s];
for (auto &[idx, val] : sc[s]) {
update(idx, val);
all_sum += val;
range_add(1, 0, q, idx, q, val);
}
seg_node info;
int ans1 = find_last(1, 0, q, k, info);
if (ans1 == -1) {
int min_ind = sg[1].min_ind;
ans[s] = all_sum - get_sum(min_ind);
} else {
int64_t cur_val = get_sum(ans1);
int lst_ind;
if (cur_val < info.mx) lst_ind = info.max_ind;
else lst_ind = info.min_ind;
int64_t res = lst_ind == q ? 0 : all_sum - get_sum(lst_ind);
if (cur_val < info.mx) ans[s] = k + res;
else ans[s] = res;
}
}
return ans;
}
