#include <bits/stdc++.h>
struct Seg {
struct Item {
long long min = 0, max = 0;
long long lazy = 0;
constexpr friend Item merge(Item l, Item r) {
return { std::min(l.min, r.min), std::max(l.max, r.max), l.lazy + r.lazy };
}
};
int size;
std::vector <Item> v;
Seg(int s) {
size = 1;
while (size < s) {
size <<= 1;
}
v.resize(size << 1);
}
inline void push(int now, int l, int r) {
v[now].min += v[now].lazy;
v[now].max += v[now].lazy;
if (r - l - 1) {
v[now * 2 + 1].lazy += v[now].lazy;
v[now * 2 + 2].lazy += v[now].lazy;
}
v[now].lazy = 0;
}
void update(int l, int r, long long val) {
update(l, r, val, 0, 0, size);
}
void update(int tl, int tr, long long val, int now, int l, int r) {
if (l >= tr || r <= tl) {
return;
}
if (l >= tl && r <= tr) {
v[now].lazy += val;
return;
}
int mid = (l + r) >> 1;
push(now, l, r);
update(tl, tr, val, now * 2 + 1, l, mid);
update(tl, tr, val, now * 2 + 2, mid, r);
push(now * 2 + 1, l, mid);
push(now * 2 + 2, mid, r);
v[now] = merge(v[now * 2 + 1], v[now * 2 + 2]);
}
int get_ind(int capacity, int now, int l, int r, long long& min, long long& max) {
if (!(r - l - 1)) {
return now;
}
int mid = (l + r) >> 1;
push(now, l, r);
push(now * 2 + 1, l, mid);
push(now * 2 + 2, mid, r);
long long new_max = std::max(v[now * 2 + 2].max, max);
long long new_min = std::min(v[now * 2 + 2].min, min);
if (new_max - new_min < (long long) capacity) {
return get_ind(capacity, now * 2 + 1, l, mid, min = new_min, max = new_max);
}
return get_ind(capacity, now * 2 + 2, mid, r, min, max);
}
long long query(int capacity) {
int ind = 0;
for (int l = 0, r = size; r - l - 1; l = (l + r) >> 1) {
push(ind, l, r);
push(ind * 2 + 1, l, (l + r) >> 1);
push(ind * 2 + 2, (l + r) >> 1, r);
ind = ind * 2 + 2;
}
long long min = 1LL << 60;
long long max = -min;
return v[get_ind(capacity, 0, 0, size, min, max)].min < min ? capacity - max + v[ind].min : v[ind].min - min;
}
};
std::vector <int> distribute_candies(std::vector <int> c, std::vector <int> l, std::vector <int> r, std::vector <int> v) {
std::vector <std::vector <std::pair <int, int>>> upd(c.size() + 1);
for (int i = 0; i < (int) v.size(); i++) {
upd[l[i]].emplace_back(i, v[i]);
upd[r[i] + 1].emplace_back(i, -v[i]);
}
Seg seg(v.size() + 2);
seg.update(0, seg.size, 1LL << 60);
seg.update(1, seg.size, -(1LL << 60));
std::vector <int> ans(c.size());
for (int i = 0; i < (int) c.size(); i++) {
for (auto p : upd[i]) {
seg.update(p.first + 2, seg.size, p.second);
}
ans[i] = seg.query(c[i]);
}
return ans;
}
