#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
// total, max prefix, max loc, min prefix, min loc
vector<ll> dummy = {0, (ll)-pow(10, 18), -1, (ll)pow(10, 18), -1};
int q;
vector<vector<ll>> st;
vector<int> v;
void merge(vector<ll>& node, vector<ll> l, vector<ll> r){
node[0] = l[0]+r[0];
node[1] = max(l[1], r[1]+l[0]);
node[2] = l[1] > r[1]+l[0] ? l[2] : r[2];
node[3] = min(l[3], r[3]+l[0]);
node[4] = l[3] > r[3]+l[0] ? l[4] : r[4];
}
void update(int pos, int val, int node=1, int tl=0, int tr=q-1){
if (tl == tr){
st[node][0] += val;
st[node][1] = max(0ll, st[node][0]);
st[node][2] = st[node][0] > 0 ? pos : pos-1;
st[node][3] = min(0ll, st[node][0]);
st[node][4] = st[node][0] < 0 ? pos : pos-1;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) update(pos, val, node*2, tl, tm);
else update(pos, val, node*2+1, tm+1, tr);
merge(st[node], st[node*2], st[node*2+1]);
}
vector<ll> query(int l, int r, int node=1, int tl=0, int tr=q-1){
if (l > r) return dummy;
if (r < tl || tr < l) return dummy;
if (l <= tl && tr <= r) return st[node];
int tm = (tl+tr)/2;
vector<ll> res = dummy;
if (l <= tm) res = query(l, r, node*2, tl, tm);
if (tm+1 <= r) merge(res, res, query(l, r, node*2+1, tm+1, tr));
return res;
}
int solve(int c){
//cout << c << endl;
int lo=-1, hi=q;
while (lo < hi-1){
int mid = (lo+hi)/2;
vector<ll> res = query(mid, q-1);
if (res[1]-res[3] >= c) lo = mid;
else hi = mid;
}
//cout << lo << endl;
if (lo == -1) return st[1][0];
if (v[lo] > 0){
//cout << "a" << endl;
if (lo == q-1) return c;
int loc = query(lo+1, q-1)[2];
//cout << loc << endl;
return c+query(loc+1, q-1)[0];
}
else {
//cout << "b" << endl;
if (lo == q-1) return 0;
int loc = query(lo+1, q-1)[4];
//cout << loc << endl;
return query(loc+1, q-1)[0];
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
::v = v;
int n = c.size();
q = l.size();
st.resize(4*q, dummy);
for (int i=0; i<q; i++) update(i, v[i]);
vector<int> res(n);
for (int i=0; i<n; i++) res[i] = solve(c[i]);
return res;
}
