#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
#define INF LLONG_MAX
#define pb push_back
using namespace std;
typedef long long ll;
vector<vector<int>> s,e;
struct segtree_min{
vector<ll> mins;
vector<ll> lazy;
int size;
void init(int n){
size=1;
while(size<n){
size*=2;
}
mins.assign(2*size,0LL);
lazy.assign(2*size,0LL);
}
void build(int x,int lx,int rx,vector<int> &a){
if(rx-lx==1){
if(lx<(int)a.size()){
mins[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(2*x+1,lx,m,a);
build(2*x+2,m,rx,a);
mins[x]=min(mins[2*x+1],mins[2*x+2]);
}
void build(vector<int> &a){
build(0,0,size,a);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1){
return;
}
mins[2*x+1]+=lazy[x];
mins[2*x+2]+=lazy[x];
lazy[2*x+1]+=lazy[x];
lazy[2*x+2]+=lazy[x];
lazy[x]=0;
}
void upd(int x,int lx,int rx,int l,int r,int v){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return;
}
if(lx>=l && rx<=r){
mins[x]+=v;
lazy[x]+=v;
return;
}
int m=(lx+rx)/2;
upd(2*x+1,lx,m,l,r,v);
upd(2*x+2,m,rx,l,r,v);
mins[x]=min(mins[2*x+1],mins[2*x+2]);
}
void upd(int l,int r,int v){
return upd(0,0,size,l,r,v);
}
ll get(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return INF;
}
if(lx>=l && rx<=r){
return mins[x];
}
int m=(lx+rx)/2;
ll s1,s2;
s1=get(2*x+1,lx,m,l,r);
s2=get(2*x+2,m,rx,l,r);
return min(s1,s2);
}
ll get(int l,int r){
return get(0,0,size,l,r);
}
};
struct segtree_max{
vector<ll> maxs;
vector<ll> lazy;
int size;
void init(int n){
size=1;
while(size<n){
size*=2;
}
maxs.assign(2*size,0LL);
lazy.assign(2*size,0LL);
}
void build(int x,int lx,int rx,vector<int> &a){
if(rx-lx==1){
if(lx<(int)a.size()){
maxs[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(2*x+1,lx,m,a);
build(2*x+2,m,rx,a);
maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
}
void build(vector<int> &a){
build(0,0,size,a);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1){
return;
}
maxs[2*x+1]+=lazy[x];
maxs[2*x+2]+=lazy[x];
lazy[2*x+1]+=lazy[x];
lazy[2*x+2]+=lazy[x];
lazy[x]=0;
}
void upd(int x,int lx,int rx,int l,int r,int v){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return;
}
if(lx>=l && rx<=r){
maxs[x]+=v;
lazy[x]+=v;
return;
}
int m=(lx+rx)/2;
upd(2*x+1,lx,m,l,r,v);
upd(2*x+2,m,rx,l,r,v);
maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
}
void upd(int l,int r,int v){
return upd(0,0,size,l,r,v);
}
ll get(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return -INF;
}
if(lx>=l && rx<=r){
return maxs[x];
}
int m=(lx+rx)/2;
ll s1,s2;
s1=get(2*x+1,lx,m,l,r);
s2=get(2*x+2,m,rx,l,r);
return max(s1,s2);
}
ll get(int l,int r){
return get(0,0,size,l,r);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
vector<int> ans(n);
s.resize(n);
e.resize(n);
for(int i=0;i<q;i++){
s[l[i]].pb(i);
e[r[i]].pb(i);
}
segtree_min stmin;
segtree_max stmax;
stmin.init(q);
stmax.init(q);
for(int i=0;i<n;i++){
for(auto x:s[i]){
stmin.upd(x,q,v[x]);
stmax.upd(x,q,v[x]);
}
int l,r,mid;
l=0;
r=q-1;
while(l<r){
mid=(l+r+1)/2;
if(stmax.get(mid,q)-stmin.get(mid,q)>=c[i]){
l=mid;
}
else{
r=mid-1;
}
}
ll res=0;
if(stmax.get(l,q)-stmin.get(l,q)>=c[i]){
if(stmax.get(l,l+1)==stmax.get(l,q)){
res=-stmin.get(l,q);
if(l+1<q){
ll mx=stmax.get(l+1,q);
if(res+mx>c[i]){
res=c[i]-mx;
}
}
}
else{
res=c[i]-stmax.get(l,q);
if(l+1<q){
ll mn=stmin.get(l+1,q);
if(res+mn<0){
res=-mn;
}
}
}
}
else{
ll mx=stmax.get(0,q);
ll mn=stmin.get(0,q);
if(mx>c[i]){
res=c[i]-mx;
}
if(mn<0){
res=-mn;
}
}
ans[i]=res+stmax.get(q-1,q);
for(auto x:e[i]){
stmin.upd(x,q,-v[x]);
stmax.upd(x,q,-v[x]);
}
}
/*
ll val[q+1];
pair<ll,ll> mn[q+1],mx[q+1];
val[0]=0;
for(int i=1;i<=q;i++){
val[i]=v[i-1];
val[i]+=val[i-1];
}
mn[q]={val[q],q};
mx[q]={val[q],q};
for(int i=q-1;i>=1;i--){
mn[i]={val[i],(ll)i};
mx[i]={val[i],(ll)i};
if(mn[i+1].first<=val[i]){
mn[i]=mn[i+1];
}
if(mx[i+1].first>=val[i]){
mx[i]=mx[i+1];
}
}
int ind=1;
while(ind<=q){
e.push_back({mx[ind].first-mn[ind].first,mx[ind].second,mn[ind].second});
ind=max(mx[ind].second,mn[ind].second)+1;
}
int sz=(int)e.size();
for(int i=0;i<n;i++){
int l,r,mid;
l=0;
r=sz-1;
while(l<r){
mid=(l+r)/2;
if(e[mid][0]<c[i]){
r=mid;
}
else{
l=mid+1;
}
}
ll res=0;
if(e[l][0]<c[i]){
if(l){
if(e[l-1][1]>e[l-1][2]){
res+=c[i]-val[e[l-1][1]];
}
else{
res-=val[e[l-1][2]];
}
}
if(val[e[l][1]]+res>c[i]){
res=c[i]-val[e[l][1]];
}
if(val[e[l][2]]+res<0){
res=-val[e[l][2]];
}
}
else{
if(e[sz-1][1]>e[sz-1][2]){
res+=c[i]-val[e[sz-1][1]];
}
else{
res-=val[e[sz-1][2]];
}
}
s[i]=val[q]+res;
}
*/
return ans;
}
