#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define pb push_back
#define ln '\n'
using i64 = long long;
const int N = 2e5 + 5;
int C;
struct SegTree{
struct Info{
i64 mn, mx, s;
Info(i64 k) : mn(min(0LL, k)), mx(max(0LL, k)), s(k) {}
Info() : mn(0), mx(0), s(0) {}
Info(const Info &a, const Info &b){
s = a.s + b.s;
mn = min(a.mn, a.s + b.mn);
mx = max(a.mx, a.s + b.mx);
}
i64 eval(){
if ( mx - mn <= C || mn < -C ){
return s - mn;
}
return C + s - mx;
}
};
vector <Info> T;
int n;
SegTree(int n) : n(n) {
T.resize(n * 4 + 5);
}
void upd(int v, int l, int r, int p, i64 x){
if ( l == r ){
T[v] = Info(T[v].s + x);
return;
}
int m = (l + r) / 2;
if ( p <= m ) upd(v * 2, l, m, p, x);
else upd(v * 2 + 1, m + 1, r, p, x);
T[v] = Info(T[v * 2], T[v * 2 + 1]);
}
void upd(int p, i64 x){ upd(1, 0, n, p, x); }
i64 qry(int v, int l, int r, Info p){
if ( l == r ){
return Info(T[v], p).eval();
}
int m = (l + r) / 2;
Info nxt = Info(T[v * 2 + 1], p);
if ( nxt.mx - nxt.mn <= C ){
return qry(v * 2, l, m, nxt);
}
return qry(v * 2 + 1, m + 1, r, p);
}
i64 qry(int c){ C = c;
return qry(1, 0, n, Info());
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int q = l.size(), n = c.size();
vector <vector<ar<int,2>>> inc(n + 1);
for ( int i = 0; i < q; i++ ){
inc[l[i]].pb({i, v[i]});
inc[r[i] + 1].pb({i, -v[i]});
}
SegTree seg(q);
vector <int> ans(n);
for ( int i = 0; i < n; i++ ){
for ( auto &[j, v]: inc[i] ){
seg.upd(j + 1, v);
}
ans[i] = seg.qry(c[i]);
}
return ans;
}
