#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int SQRT = 350;
const ll INF = 1e18;
struct Node {
ll MN, MX;
};
struct Segtree {
Node val;
ll l, r, lz = 0;
Segtree *lf, *rg;
void build() {
val = {0, 0};
if (l == r) return;
ll mid = (l+r)/2;
lf = new Segtree(), rg = new Segtree();
lf->l = l, lf->r = mid, rg->l = mid+1, rg->r = r;
lf->build(), rg->build();
}
void push() {
lf->val.MN += lz;
lf->val.MX += lz;
rg->val.MN += lz;
rg->val.MX += lz;
lf->lz += lz;
rg->lz += lz;
lz = 0;
}
void update(ll x, ll y, ll z) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
val.MN += z;
val.MX += z;
lz += z;
return;
}
push();
lf->update(x, y, z), rg->update(x, y, z);
val = {min(lf->val.MN, rg->val.MN), max(lf->val.MX, rg->val.MX)};
}
Node query(ll x, ll y) {
if (l > y || r < x) return {INF, -INF};
if (l >= x && r <= y) return val;
push();
Node a = lf->query(x, y), b = rg->query(x, y);
return {min(a.MN, b.MN), max(a.MX, b.MX)};
}
} sg;
vector <int> distribute_candies(vector <int> C, vector <int> L, vector <int> R, vector <int> V) {
int N = C.size();
int Q = L.size();
vector <pair<int, int>> sweep[N+5];
for (int i = 1; i <= Q; i++) {
sweep[L[i-1]].push_back({i, V[i-1]});
sweep[R[i-1]+1].push_back({i, -V[i-1]});
}
vector <int> ans(N);
sg.l = 0, sg.r = Q;
sg.build();
for (int i = 0; i < N; i++) {
for (auto [idx, z] : sweep[i]) {
sg.update(idx, Q, z);
}
ll lf = 0, rg = Q, ptr = -1;
for (;lf <= rg;) {
ll mid = (lf+rg)/2;
Node cur = sg.query(mid, Q);
if (cur.MX-cur.MN >= C[i]) {
ptr = mid;
lf = mid+1;
}
else rg = mid-1;
}
if (ptr == -1) {
ans[i] = sg.query(Q, Q).MN;
}
else {
Node cur = sg.query(ptr, Q);
Node st = sg.query(ptr, ptr);
Node en = sg.query(Q, Q);
if (st.MN == cur.MN) {
ans[i] = C[i]+(en.MN-cur.MX);
}
else {
ans[i] = en.MN-cur.MN;
}
}
}
return ans;
}
