#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=1e9;
struct node
{
ll maxval,minval,sum;
};
node merge(node n1,node n2)
{
n1.maxval=max(n1.maxval,n1.sum+n2.maxval);
n1.minval=min(n1.minval,n1.sum+n2.minval);
n1.sum=n1.sum+n2.sum;
return n1;
}
struct segment_tree
{
node tree[4*MAXN];
void build(int l,int r,int idx)
{
if(l==r)
{
tree[idx].maxval=0;
tree[idx].minval=0;
tree[idx].sum=0;
return;
}
int mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
void update(int l,int r,int idx,int q,int val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
tree[idx].maxval=val;
tree[idx].minval=val;
tree[idx].sum=val;
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,q,val);
update(mid+1,r,idx*2+1,q,val);
tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
node query(int l,int r,int idx,int ql,int qr)
{
if(l>=ql&&r<=qr)return tree[idx];
int mid=(l+r)/2;
if(qr<=mid)return query(l,mid,idx*2,ql,qr);
else if(ql>mid)return query(mid+1,r,idx*2+1,ql,qr);
else return merge(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
}t;
struct update
{
int when,v;
};
vector<update>ul[MAXN],ur[MAXN];
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
ll n = c.size(),q=l.size();
vector<int>s(n,0);
ul[0].push_back({1,+INF});
ur[n-1].push_back({1,+INF});
ul[0].push_back({2,-INF});
ur[n-1].push_back({2,-INF});
for(int i=0;i<q;i++)
{
ul[l[i]].push_back({i+3,v[i]});
ur[r[i]].push_back({i+3,v[i]});
}
t.build(1,q+2,1);
for(int idx=0;idx<n;idx++)
{
for(auto xd:ul[idx])
{
t.update(1,q+2,1,xd.when,xd.v);
}
int low=1,high=q+2,mid,ans;
node rupert;
while(low<=high)
{
mid=(low+high)/2;
rupert=t.query(1,q+2,1,mid,q+2);
if(rupert.maxval-rupert.minval>=c[idx])
{
ans=mid;
low=mid+1;
}
else
{
high=mid-1;
}
}
rupert=t.query(1,q+2,1,ans,q+2);
int minval=rupert.minval;
int maxval=rupert.maxval;
int sum=rupert.sum;
//cout<<idx<<":\n";
//cout<<minval<<" "<<maxval<<" "<<ans<<endl;
rupert=t.query(1,q+2,1,ans,ans);
//cout<<rupert.maxval<<endl;
if(rupert.maxval==maxval)
{
s[idx]=sum-minval;
}
else
{
s[idx]=c[idx]-(maxval-sum);
}
for(auto xd:ur[idx])
{
t.update(1,q+2,1,xd.when,0);
}
}
return s;
}
