#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5;
struct seg{
ll l,r,lz=0;
seg *lf,*rg;
pair<ll,ll>isi;
void build(ll x,ll y){
l=x,r=y; isi={0,0};
if(l==r){
return;
}
ll mid=(l+r)/2;
lf=new seg(),rg=new seg();
lf->build(l,mid),rg->build(mid+1,r);
}
void apply(ll val){
lz+=val;
isi.first+=val,isi.second+=val;
}
void prop(){
if(lz==0 || l==r)return;
lf->apply(lz),rg->apply(lz);
lz=0;
}
void update(ll posl,ll posr,ll val){
if(l>posr || r<posl)return;
if(l>=posl && r<=posr){
apply(val); return;
}
prop();
lf->update(posl,posr,val),rg->update(posl,posr,val);
isi={min(lf->isi.first,rg->isi.first),max(lf->isi.second,rg->isi.second)};
}
pair<ll,ll> query(ll posl,ll posr){
if(l>posr || r<posl)return {1e18,-1e18};
if(l>=posl && r<=posr)return isi;
prop();
pair<ll,ll> a=lf->query(posl,posr);
pair<ll,ll> b=rg->query(posl,posr);
return {min(a.first,b.first),max(a.second,b.second)};
}
};
vector<pair<ll,ll> >event[maxn+2];
seg slv;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(),qu=l.size();
vector<int> s(n,0);
for(int q=0;q<qu;q++){
event[l[q]].push_back({q+1,v[q]});
event[r[q]+1].push_back({q+1,-v[q]});
}
slv.build(0,qu);
for(int q=0;q<n;q++){
for(auto [x,y] : event[q]){
slv.update(x,qu,y);
}
// cari max(pref[ans...qu])-min(pref[ans...qu])>=c[q]
int l=0,r=qu,ans=-1;
while(l<=r){
int mid=(l+r)/2;
pair<ll,ll>apa=slv.query(mid,qu);
if(apa.second-apa.first>=c[q]){
ans=mid; l=mid+1;
}
else{
r=mid-1;
}
}
// berarti habis ans ada yang kosong/penuh
pair<ll,ll>apa=slv.query(ans,qu);
pair<ll,ll>awal=slv.query(ans,ans);
pair<ll,ll>akh=slv.query(qu,qu);
if(awal.first==apa.first){
// berarti nanti penuh
s[q]=c[q]+(akh.first-apa.second);
}
else{
s[q]=akh.first-apa.first;
}
}
return s;
}
