#include "candies.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
inline void chmin(int &x, const int &v) {
x = min(x, v);
}
inline void chmax(int &x, const int &v) {
x = max(x, v);
}
const int MAXN = 200'000;
const int MAXQ = MAXN;
const int INF = 1e18;
// single point add, min/max sum query on suffixs
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
struct Node {
int mns, mxs, sum;
// min suffix, max suffix, sum
} a[MAXN * 4 + 10];
void pull(int id) {
a[id].mns = min(a[L(id)].mns + a[R(id)].sum, a[R(id)].mns);
a[id].mxs = max(a[L(id)].mxs + a[R(id)].sum, a[R(id)].mxs);
a[id].sum = a[L(id)].sum + a[R(id)].sum;
}
// initialize
void build() {
memset(a, 0, sizeof(a));
}
// add value for a single point
void single_add(int id, int l, int r, int pos, int val) {
if(l == r) {
a[id].mns += val;
a[id].mxs += val;
a[id].sum += val;
return;
}
int m = l + (r - l) / 2;
if(pos <= m) single_add(L(id), l, m, pos, val);
if(pos > m) single_add(R(id), m + 1, r, pos, val);
pull(id);
}
// search for maximum suffix sum for all [i > pos]
// return: {max suf, suf sum}
pii max_suf(int id, int l, int r, int pos) {
if(pos > r) return pii(-INF, 0);
if(pos <= l) return pii(a[id].mxs, a[id].sum);
int m = l + (r - l) / 2;
pii pl = max_suf(L(id), l, m, pos);
pii pr = max_suf(R(id), m + 1, r, pos);
return pii(max(pl.F + pr.S, pr.F), pl.S + pr.S);
}
// search for minimum suffix sum for all [i > pos]
// return: {min suf, suf sum}
pii min_suf(int id, int l, int r, int pos) {
if(pos > r) return pii(INF, 0);
if(pos <= l) return pii(a[id].mns, a[id].sum);
int m = l + (r - l) / 2;
pii pl = min_suf(L(id), l, m, pos);
pii pr = min_suf(R(id), m + 1, r, pos);
return pii(min(pl.F + pr.S, pr.F), pl.S + pr.S);
}
} seg;
// search for last (rightmost) position where [dif > c]
int search(int q, int c) {
int lo = 0, hi = q + 1;
while(hi - lo > 1) {
int mi = (hi + lo) / 2;
int dif = seg.max_suf(0, 0, q + 1, mi).F - seg.min_suf(0, 0, q + 1, mi).F;
if(dif > c) lo = mi;
else hi = mi;
}
return lo;
}
vector<i32> distribute_candies(vector<i32> C, vector<i32> LE, vector<i32> RI, vector<i32> VAL) {
int n = sz(C);
int q = sz(VAL);
vector<int> a(q + 2, 0);
a[0] = INF;
seg.build();
seg.single_add(0, 0, q + 1, 0, a[0]);
struct Event { int time, pos, val; };
vector<Event> ev;
For(i, 0, q - 1) {
ev.push_back({LE[i], i + 1, -VAL[i]});
ev.push_back({RI[i] + 1, i + 1, VAL[i]});
}
sort(all(ev), [&](const Event &e1, const Event &e2) {
return e1.time > e2.time;
});
vector<int> ans(n);
For(i, 0, n - 1) {
while(sz(ev) && ev.back().time == i) {
auto e = ev.back(); ev.pop_back();
a[e.pos] += e.val;
seg.single_add(0, 0, q + 1, e.pos, e.val);
}
int c = C[i];
int pos = search(q, c);
if(a[pos] < 0) ans[i] = c - seg.max_suf(0, 0, q + 1, pos + 1).F;
else ans[i] = -seg.min_suf(0, 0, q + 1, pos + 1).F;
}
return vector<i32>(all(ans));
}
/*
3
10 15 13
2
0 2 20
0 1 -11
0 4 13
*/
