#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include "candies.h"
using namespace std;
const int MAX_N=2e5+5;
const int BUFF=500;
vector<int>cap;
vector<long long>a,nxt;
vector<pair<int,long long>>queries;
set<pair<int,long long>>curqueries;
void solve(int l,int r)
{
queries.clear();
for(auto x:curqueries)queries.push_back(x);
vector<long long>p,nxt;
p.resize((int)queries.size());
nxt.resize((int)queries.size());
p[0]=queries[0].second;
for(int i=1;i<queries.size();i++)
{
p[i]=p[i-1]+queries[i].second;
}
nxt[queries.size()-1]=queries.size()-1;
for(int i=queries.size()-2;i>=0;i--)
{
nxt[i]=queries.size()-1;
for(int j=i+1;j<queries.size();j++)
{
if(p[j]<p[i]){nxt[i]=j;break;}
}
}
vector<pair<long long,int>>nums;
for(int i=l;i<=r;i++)
{
nums.push_back({a[i],i});
}
sort(nums.begin(),nums.end());
int id=0;
for(auto [num,i]:nums)
{
while(p[id]+a[i]>0 && id<p.size())id++;
if(id==p.size())
{
a[i]-=p.back();
}
else
{
a[i]=min((long long)cap[i],p.back()-p[id]);
}
}
}
vector<pair<pair<int,int>,pair<int,int>>>buffer;
vector<pair<int,int>>beg[MAX_N],en[MAX_N];
int N;
void clearbuffer()
{
for(int i=0;i<=N;i++)
{
beg[i].clear();en[i].clear();
}
for(auto [f,s]:buffer)
{
int l,r,i,val;
l=f.first;r=f.second;i=s.first;val=s.second;
beg[l].push_back({i,val});
en[r+1].push_back({i,val});
}
curqueries.clear();
int prevpoint=-1;
for(int i=0;i<=N;i++)
{
if(en[i].size() && prevpoint!=-1)
{
solve(prevpoint,i-1);
}
for(auto x:en[i])
{
curqueries.erase(x);
}
if(en[i].size() && curqueries.size())prevpoint=i-1;
if(curqueries.size()==0)prevpoint=-1;
if(beg[i].size() && prevpoint!=-1)
{
solve(prevpoint,i-1);
}
for(auto x:beg[i])
{
curqueries.insert(x);
}
if(beg[i].size())prevpoint=i;
}
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v)
{
cap=c;
N=cap.size();
a.resize((int)cap.size());
for(int i=0;i<l.size();i++)
{
buffer.push_back({{l[i],r[i]},{i,v[i]}});
if(buffer.size()==BUFF)
{
clearbuffer();
}
}
if(buffer.size())
{
clearbuffer();
}
vector<int>aa;
for(int x:a)
{
aa.push_back(x);
}
return aa;
}
