#include"candies.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
int n,days;
const int TREE_SIZE=1<<11;
vector<ll>mn;
vector<ll>mx;
void tree_init(){
mn.resize(TREE_SIZE*2);
mx.resize(TREE_SIZE*2);
}
void update_node(int node){
if(node>=TREE_SIZE){
mn[node]=mx[node];
return;
}
mn[node]=min(mn[2*node],mn[2*node+1]);
mx[node]=max(mx[2*node],mx[2*node+1]);
}
void tree_add(int node,int l,int r,int pos,int val){
//cout<<l<<" "<<r<<endl;
if(r<=pos)
return;
if(node>=TREE_SIZE){
mx[node]+=val;
update_node(node);
return;
}
int m=(l+r)/2;
tree_add(2*node,l,m,pos,val);
tree_add(2*node+1,m,r,pos,val);
update_node(node);
}
void tree_add(int pos,int val){
tree_add(1,0,TREE_SIZE,pos,val);
}
int tree_get(int bound){
/*for(int i=0;i<days;i++)
cout<<mn[TREE_SIZE+i]<<" ";
cout<<endl;*/
int min_i=days-1,max_i=days-1;
for(int i=days-1;i>=0;i--){
if(mn[TREE_SIZE+i]<mn[TREE_SIZE+min_i])
min_i=i;
if(mn[TREE_SIZE+i]>mn[TREE_SIZE+max_i])
max_i=i;
if(mn[TREE_SIZE+max_i]-mn[TREE_SIZE+min_i]>=bound){
if(max_i==i){
return mn[TREE_SIZE+days-1]-mn[TREE_SIZE+min_i];
}else{
return bound-(mn[TREE_SIZE+max_i]-mn[TREE_SIZE+days-1]);
}
}
}
return mn[TREE_SIZE+days-1]-mn[TREE_SIZE+min_i];
}
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);
if(n>2000||days>2001)
return{};
for(int i=0;i<days-1;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;
}
