#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=2e5+5;
ll pre[mxN];
ll br[mxN];
ll v[mxN], c[mxN];
vector<array<ll, 3>> stk;
vll con;
ll timer;
ll id(ll tar){
return lower_bound(con.begin(), con.end(), tar)-con.begin();
}
ll getsum(ll a, ll b){
return pre[b+1]-pre[a];
}
ll getval(ll idx){
ll lef=0, rig=stk.size()-1;
ll good=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(stk[mid][0]>=idx){
good=mid;
lef=mid+1;
}
else{
rig=mid-1;
}
}
if(good==-1){
return pre[timer];
}
ll prevbr=stk[good][1];
ll re=pre[timer]-pre[prevbr+1];
if(stk[good][2]==1){
re+=con[idx];
}
return re;
}
}
vector<int> distribute_candies(vector<int> C, vector<int> l,
vector<int> r, vector<int> V) {
ll n = C.size();
ll q=l.size();
for(ll i=0;i<n;i++){
c[i]=C[i];
con.pb(c[i]);
}
pre[0]=0;
for(ll i=0;i<q;i++){
v[i]=V[i];
pre[i+1]=pre[i]+v[i];
}
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
for(ll i=0;i<q;i++){
timer=i;
// cout<<"i: "<<i<<'\n';
// cout<<"stk: "<<'\n';
// for(auto &it:stk){
// cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<'\n';
// }
// for(ll j=0;j<(ll) con.size();j++){
// cout<<con[j]<<" val: "<<getval(j)<<'\n';
// }
if(v[i]>0){
ll lef=0, rig=(ll) con.size()-1;
ll good=-1;
auto check=[&](ll tar){
if(con[tar]-getval(tar)>v[i]){
return true;
}
return false;
};
while(lef<=rig){
ll mid=(lef+rig)/2;
if(check(mid)){
good=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
if(good==-1){
br[i]=n;
while(!stk.empty() && stk.back()[0]<=n){
stk.pop_back();
}
stk.pb({n, i, 1});
}
else{
good--;
if(good>=0){
br[i]=good;
while(!stk.empty() && stk.back()[0]<=br[i]){
stk.pop_back();
}
stk.pb({br[i], i, 1});
}
}
}
else{
ll lef=0, rig=(ll) con.size()-1;
ll good=-1;
auto check=[&](ll tar){
if(getval(tar)>-v[i]){
return true;
}
return false;
};
while(lef<=rig){
ll mid=(lef+rig)/2;
if(check(mid)){
good=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
if(good==-1){
br[i]=n;
while(!stk.empty() && stk.back()[0]<=n){
stk.pop_back();
}
stk.pb({n, i, 0});
}
else{
good--;
if(good>=0){
br[i]=good;
while(!stk.empty() && stk.back()[0]<=br[i]){
stk.pop_back();
}
stk.pb({br[i], i, 0});
}
}
}
}
timer=q;
vll a(n);
for(ll i=0;i<n;i++){
a[i]=getval(id(c[i]));
}
vector<int> re(n);
for(ll i=0;i<n;i++){
re[i]=a[i];
}
return re;
}
