#include"candies.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
int n,days;
vector<ll>vec;
void tree_init(){
vec.resize(days);
}
void tree_add(int pos,int val){
for(int i=pos;i<days;i++)
vec[i]+=val;
int curr_inc=0;
for(int i=0;i<days;i++){
vec[i]+=curr_inc;
if(vec[i]<0){
curr_inc-=vec[i];
vec[i]=0;
}
}
}
int tree_get(int bound){
/*for(ll i:vec)
cout<<i<<" ";
cout<<endl;*/
int min_i=days-1,max_i=days-1;
for(int i=days-1;i>=0;i--){
if(vec[i]<vec[min_i])
min_i=i;
if(vec[i]>vec[max_i])
max_i=i;
if(vec[max_i]-vec[min_i]>=bound){
if(max_i==i){
return vec[days-1]-vec[min_i];
}else{
return bound-(vec[max_i]-vec[days-1]);
}
}
}
return vec[days-1];
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
n=(int)c.size();
days=(int)v.size()+1;
vector<vector<pair<int,int>>>events;
events.resize(n+1);
for(int i=0;i<days;i++){
events[l[i]].push_back({i+1,v[i]});
events[r[i]+1].push_back({i+1,-v[i]});
}
vector<int>s(n);
tree_init();
for(int i=0;i<n;i++){
for(auto event:events[i])
tree_add(event.first,event.second);
s[i]=tree_get(c[i]);
}
return s;
}
