#include "candies.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 2e5+5;
const ll inf = 1LL << 60;
vector<int> L, R, V;
int q;
int bound(int l, int r, int x){
if(x < l) return l;
if(x > r) return r;
return x;
}
namespace Segtree{
struct node{
ll mxp = 0, mnp = 0, s = 0;
node(){}
node(ll v) : mxp(max(v, 0LL)), mnp(min(v, 0LL)), s(v){};
} t[N * 4];
node merge(node a, node b){
if(a.mxp == inf || b.mxp == inf) return a.mxp == inf ? b : a;
node ret;
ret.mxp = max(a.mxp, a.s + b.mxp);
ret.mnp = min(a.mnp, a.s + b.mnp);
ret.s = a.s + b.s;
return ret;
}
void build(int v = 0, int l = 0, int r = q - 1){
if(l == r){
t[v] = node(0); return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m + 1, r);
t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
}
void add(int id, int v = 0, int tl = 0, int tr = q - 1){
if(tl == tr){
t[v] = node(V[tl]); return;
}
int tm = (tl + tr) / 2;
if(id <= tm){
add(id, v * 2 + 1, tl, tm);
}else{
add(id, v * 2 + 2, tm + 1, tr);
}
t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
}
void remove(int id, int v = 0, int tl = 0, int tr = q - 1){
if(tl == tr){
t[v] = node(0); return;
}
int tm = (tl + tr) / 2;
if(id <= tm){
remove(id, v * 2 + 1, tl, tm);
}else{
remove(id, v * 2 + 2, tm + 1, tr);
}
t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
}
int query(int c){
int v = 0, tl = 0, tr = q - 1;
node cur {0};
while(tl != tr){
int tm = (tl + tr) / 2;
node nxt = merge(t[v * 2 + 2], cur);
if(nxt.mxp - nxt.mnp <= c){
cur = nxt;
tr = tm;
v = v * 2 + 1;
}else{
tl = tm + 1;
v = v * 2 + 2;
}
}
node nxt = merge(t[v], cur);
if(nxt.mxp - nxt.mnp <= c){
cur = nxt;
tr--;
}
int st = (tr < 0 ? 0 : bound(0, c, V[tr]));
return bound(-cur.mnp, c - cur.mxp, st) + cur.s;
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
vector<int> ans(n);
q = l.size();
::L = l, ::R = r, ::V = v;
vector<pii> Q;
for(int i = 0; i < q; i++){
Q.push_back({l[i], i+1});
Q.push_back({r[i]+1, -i-1});
}
sort(Q.begin(), Q.end());
int qi = 0;
for(int i = 0; i < n; i++){
while(qi < Q.size() && Q[qi].fi <= i){
if(Q[qi].se > 0) Segtree::add(Q[qi].se - 1);
else Segtree::remove(-Q[qi].se - 1);
qi++;
}
ans[i] = Segtree::query(c[i]);
}
return ans;
}
