#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 2e5 + 1;
const ll inf = 1e18;
ll mn[M*2], mx[M*2], lz[M*2];
int m;
void push(int v,int lc,int rc)
{
mn[lc]+=lz[v], mx[lc]+=lz[v], lz[lc]+=lz[v];
mn[rc]+=lz[v], mx[rc]+=lz[v], lz[rc]+=lz[v];
lz[v]=0;
}
void modify(int l,int r,int x,int v=0,int s=0,int e=m+1)
{
if (s>=r or l>=e) return;
if (l<=s && e<=r)
{
mn[v]+=x, mx[v]+=x, lz[v]+=x;
return;
}
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
push(v,lc,rc);
modify(l,r,x,lc,s,mid);
modify(l,r,x,rc,mid,e);
mn[v]=min(mn[lc],mn[rc]), mx[v]=max(mx[lc], mx[rc]);
}
pair<ll,ll> get(int l,int r,int v=0,int s=0,int e=m+1)
{
if (l>=e or r<=s) return {inf,-inf};
if (l<=s && e<=r) return {mn[v],mx[v]};
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
push(v,lc,rc);
pair<ll,ll> p=get(l,r,lc,s,mid), p1=get(l,r,rc,mid,e);
return {min(p.first,p1.first),max(p.second,p1.second)};
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
m=l.size();
int n=c.size();
vector<int> ad[n], rem[n];
for (int i=0;i<m;i++)
ad[l[i]].push_back(i), rem[r[i]].push_back(i);
vector<int> ans(n);
for (int i=0;i<n;i++)
{
for (int x:ad[i])
modify(x+1,m+1,v[x]);
if (mx[0]-mn[0]>c[i])
{
int s=0, e=m+1;
while (s+1<e)
{
int mid=(s+e)/2;
pair<int,int> p=get(mid,m+1);
if (p.second-p.first>=c[i]) s=mid;
else e=mid;
}
pair<int,int> p=get(s,m+1), p1=get(s+1,m+1), p2=get(m,m+1);
if (p.first==p1.first)
ans[i]=p2.first-p1.first;
else
ans[i]=c[i]-p1.second+p2.first;
}
else
ans[i]=get(m,m+1).first-mn[0]*(mn[0]>=0);
for (int x:rem[i])
modify(x+1,m+1,-v[x]);
}
return ans;
}
