#include "candies.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
typedef long long ll;
pair<ll,int> operator+(pair<ll,int> a,pair<ll,int> b){
return {a.fs+b.fs,b.sc};
}
struct no{
ll sum=0;
pair<ll,int> mn={0,0},mx={0,0};
ll ans=0;
};
struct ST{
vector<no> st;
void init(int x){
st.resize(4*x);
build(0,0,x-1);
}
void build(int v,int L,int R){
if(L==R){
st[v].mn.sc=st[v].mx.sc=L;
return;
}
int m=(L+R)/2;
build(2*v+1,L,m);
build(2*v+2,m+1,R);
merge(st[v],st[2*v+1],st[2*v+2]);
}
void merge(no& v,no& a,no& b){
v.sum=a.sum+b.sum;
v.mn=min(b.mn,pair<ll,int>(b.sum,-1)+a.mn);
v.mx=max(b.mx,pair<ll,int>(b.sum,-1)+a.mx);
v.ans=max({a.ans,b.ans,(b.sum+a.mx.fs)-b.mn.fs,b.mx.fs-(b.sum+a.mn.fs)});
}
void update(int v,int L,int R,int p,int x){
if(L==R){
st[v].sum=x;
st[v].mn.fs=st[v].mx.fs=x;
return;
}
int m=(L+R)/2;
if(p<=m){
update(2*v+1,L,m,p,x);
}
else{
update(2*v+2,m+1,R,p,x);
}
merge(st[v],st[2*v+1],st[2*v+2]);
}
no find(int v,int L,int R,int c,no& a){
if(L==R){
no h;
merge(h,st[v],a);
return h;
}
int m=(L+R)/2;
no h;
merge(h,st[2*v+2],a);
if(h.ans>c){
return find(2*v+2,m+1,R,c,a);
}
else{
a=h;
return find(2*v+1,L,m,c,a);
}
}
}st;
vector<int> distribute_candies(vector<int> w, vector<int> l,
vector<int> r, vector<int> v) {
int n=w.size();
vector<int> ans(n);
int q=l.size()+2;
st.init(q);
st.update(0,0,q-1,0,2e9);
vector<vector<pair<int,int> > > upd(n),del(n);
for(int i=0;i<q-2;i++){
upd[l[i]].push_back({i+1,v[i]});
del[r[i]].push_back({i+1,v[i]});
}
for(int i=0;i<n;i++){
for(auto h:upd[i]){
st.update(0,0,q-1,h.fs,-h.sc);
}
no e;
e.mn.sc=e.mx.sc=q-1;
auto d=st.find(0,0,q-1,w[i],e);
if(d.mx.fs-e.mn.fs>w[i]){
ans[i]=-e.mn.fs;
}
else{
ans[i]=w[i]-e.mx.fs;
}
for(auto h:del[i]){
st.update(0,0,q-1,h.fs,0);
}
}
return ans;
}
