#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){
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;
}
if (lo == -1 || v[lo] < 0){
if (lo == q-1) return 0;
vector<ll> res = query(lo+1, q-1);
int loc = query(lo+1, q-1)[4];
return query(loc+1, q-1)[0];
}
else {
if (lo == q-1) return c;
int loc = query(lo+1, q-1)[2];
return c+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, 0);
vector<pair<int,int>> ev;
for (int i=0; i<q; i++){
ev.push_back({l[i], i});
ev.push_back({r[i]+1, i});
}
sort(ev.begin(), ev.end());
vector<int> res(n);
int cur = 0;
for (int i=0; i<n; i++){
while (cur < 2*q && ev[cur].first == i){
if (i == l[ev[cur].second]) update(ev[cur].second, v[ev[cur].second]);
else update(ev[cur].second, -v[ev[cur].second]);
cur++;
}
res[i] = solve(c[i]);
}
return res;
}
