#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/hp/contests/debug.h"
#else
#define debug(...) void(37)
#endif
struct mapping {
int64_t dist = 0;
int64_t compressed = 0;
};
mapping unite(mapping l, mapping r) {
mapping res;
int64_t start = max(r.compressed, l.dist);
res.compressed = l.compressed + start - l.dist;
res.dist = r.dist + start - r.compressed;
return res;
}
struct two_sided_mapping {
mapping lower, upper;
two_sided_mapping() { }
two_sided_mapping(const int& x) {
lower = upper = mapping{};
if (x > 0) {
lower.compressed = x;
upper.dist = x;
} else {
upper.compressed = -x;
lower.dist = -x;
}
}
int64_t compressed() {
return lower.compressed + upper.compressed;
}
};
two_sided_mapping unite(two_sided_mapping l, two_sided_mapping r) {
l.lower = unite(l.lower, r.lower);
l.upper = unite(l.upper, r.upper);
return l;
}
using T = two_sided_mapping;
#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
struct SegTree {
vector<T> tree;
int n;
SegTree(int _n) : n(_n) {
tree.resize(2 * n - 1);
}
void modify(int v, int l, int r, int p, T x) {
if (l == r) {
tree[v] = x;
return;
}
def;
if (p <= mid) {
modify(v + 1, l, mid, p, x);
} else {
modify(rv, mid + 1, r, p, x);
}
tree[v] = unite(tree[rv], tree[v + 1]);
}
void modify(int p, int x) {
modify(0, 0, n - 1, p, T(x));
}
pair<int, T> find_last(int cap) {
int v = 0, l = 0, r = n - 1;
T res;
while (l < r) {
def;
auto test = unite(res, tree[rv]);
if (test.compressed() < cap) {
swap(res, test);
v = v + 1;
r = mid;
} else {
v = rv;
l = mid + 1;
}
}
auto test = unite(res, tree[v]);
if (test.compressed() < cap) {
--l;
assert(l == -1);
swap(test, res);
}
return {l, res};
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
int n = int(c.size());
int q = int(l.size());
vector<vector<int>> events(n + 1);
for (int i = 0; i < q; ++i) {
events[l[i]].push_back(i);
events[r[i] + 1].push_back(~i);
}
SegTree act(q + 1);
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
for (auto x : events[i]) {
if (x >= 0) {
act.modify(x, v[x]);
} else {
act.modify(~x, 0);
}
}
auto[last, res] = act.find_last(c[i]);
if (last == -1) {
ans[i] = res.lower.compressed;
} else if (v[last] > 0) {
ans[i] = c[i] - res.upper.compressed;
} else {
ans[i] = res.lower.compressed;
}
}
return ans;
}
