#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
#define ll long long
const ll LOG = 20;
const ll N = 2e5 + 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e17;
namespace seggy{
ll mn[4 * N], mx[4 * N], lz[4 * N];
void push(ll k,ll tl,ll tr){
mn[k] += lz[k], mx[k] += lz[k];
if(tl != tr)lz[k * 2] += lz[k], lz[k *2 + 1] += lz[k];
lz[k] =0;
}
void upd(ll k,ll tl,ll tr,ll l,ll r,ll v){
push(k, tl, tr);
if(tl > r || l > tr)return;
if(l <= tl && tr <= r){
lz[k] += v;
push(k, tl, tr);
return;
}
ll tm = (tl + tr) / 2;
upd(k *2, tl, tm, l, r, v);
upd(k * 2 + 1, tm + 1, tr ,l, r, v);
mn[k] = min(mn[k *2], mn[k *2 + 1]);
mx[k] = max(mx[k * 2], mx[k *2 + 1]);
}
ll qry(ll k,ll tl,ll tr,ll v){
push(k, tl, tr);
if(tl == tr)return mn[k];
ll tm = (tl + tr) / 2;
if(mx[k *2 + 1] + lz[k *2 + 1]>= v)return qry(k * 2 + 1, tm + 1, tr, v);
else return min(mn[k *2 + 1] + lz[k *2 + 1], qry(k * 2, tl, tm, v));
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L,vector<int> R, vector<int> V) {
ll n = C.size(), q = L.size();
vector<ll> be[n], en[n];
for(ll i = 0;i < q;i++){
be[L[i]].push_back(i);
en[R[i]].push_back(i);
}
vector<int> res(n);
for(ll i = 0;i < n;i++){
for(auto j: be[i])seggy::upd(1, 0, q - 1, 0, j, V[j]);
// cout<<i<<endl;
ll lo = 1, hi = C[i] + 1;
ll ans;
while(lo <= hi){
ll tm = (lo + hi) / 2;
ll mn = min(0ll, seggy::qry(1, 0, q - 1, tm));
if(seggy::mx[1] < tm)mn = -INF;
if(tm - mn > C[i]){
ans = tm;
hi = tm - 1;
}else lo = tm + 1;
}
res[i] = ans - 1;
for(auto j: en[i])seggy::upd(1, 0, q - 1, 0, j, -V[j]);
}
return res;
}
