#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
struct st{
ll mn=0,mx=0;
};
ll n,q,sum[mxn],lazy[4*mxn],arr[mxn],tree2[mxn];
vector<int>start[mxn],finish[mxn];
st tree[mxn*4];
void update2(int idx,ll val){
while(idx<=q){
tree2[idx]+=val;
idx+=(idx&(-idx));
}
}
ll query2(int idx){
ll ans=0;
while(idx>0){
ans+=tree2[idx];
idx-=(idx&(-idx));
}
return ans;
}
void relax(int node,int l,int r){
if(l!=r){
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
}
tree[node].mn+=lazy[node];
tree[node].mx+=lazy[node];
lazy[node]=0;
}
void update(int node,int l,int r,int ql,int qr,int val){
if(lazy[node]){
relax(node,l,r);
}
if(r<ql||l>qr) return;
if(ql<=l&&r<=qr){
lazy[node]=val;
relax(node,l,r);
return;
}
int m=(l+r)/2;
update(2*node,l,m,ql,qr,val);
update(2*node+1,m+1,r,ql,qr,val);
tree[node].mn=min(tree[2*node].mn,tree[2*node+1].mn);
tree[node].mx=max(tree[2*node].mx,tree[2*node+1].mx);
}
st query(int node,int l,int r,int ql,int qr){
if(l>qr||r<ql){
st ans;
ans.mn=INF;
ans.mx=-INF;
return ans;
}
if(lazy[node]){
relax(node,l,r);
}
if(ql<=l&&r<=qr){
return tree[node];
}
int m=(l+r)/2;
st x=query(2*node,l,m,ql,qr);
st y=query(2*node+1,m+1,r,ql,qr);
st ans;
ans.mn=min(x.mn,y.mn);
ans.mx=max(x.mx,y.mx);
return ans;
}
vector<int> distribute_candies(vector<int> c, vector<int> x, vector<int> y, vector<int> vq) {
n = c.size();
q=x.size();
int sz=q;
for(int i=0;i<q;i++){
arr[i+1]=vq[i];
}
for(int i=0;i<q;i++){
start[x[i]].pb(i);
finish[y[i]+1].pb(i);
}
vector<int>ans;
for(int id=0;id<n;id++){
for(int v:start[id]){
update(1,1,q,v+1,q,vq[v]);
update2(v+1,vq[v]);
}
for(int v:finish[id]){
update(1,1,q,v+1,q,-vq[v]);
update2(v+1,-vq[v]);
}
int lim=c[id];
int pos=0;
int l=1,r=q;
while(l<=r){
int m=(l+r)/2;
st res=query(1,1,q,m,q);
if(res.mx-res.mn>lim){
l=m+1;
}
else{
r=m-1;
}
}
pos=l-1;
ll mxx=0,mnn=0,sum=0;
if(pos>0){
st res=query(1,1,q,pos,q);
mxx=res.mx;
mnn=res.mn;
sum=query2(pos);
}
else{
st res=query(1,1,q,1,q);
mxx=max(res.mx,mxx);
mnn=min(res.mn,mnn);
sum=0;
}
if(mxx-sum>lim){
ans.pb(lim-(mxx-query2(q)));
}
else{
ans.pb(query2(q)-mnn);
}
}
return ans;
}
