#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)2e5 + 100;
const ll inf = (ll)1e18;
struct Node{
ll mx;
ll low;
ll lzy;
};
Node T[N * 4 + 512];
void push(int node, int cl, int cr){
T[node].mx += T[node].lzy;
T[node].low += T[node].lzy;
if(cl != cr){
T[node * 2].lzy += T[node].lzy;
T[node * 2 + 1].lzy += T[node].lzy;
}
T[node].lzy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, ll v){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
T[node].lzy += v;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, v);
upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
T[node].mx = max(T[node * 2].mx, T[node * 2 + 1].mx);
T[node].low = min(T[node * 2].low, T[node * 2 + 1].low);
}
vector<pii> Q[N];
ll getval(int node, int cl, int cr, int tl, int tr, int ff){
push(node, cl, cr);
if(cr < tl || cl > tr) {
if(ff == 0) return inf;
else return -inf;
}
if(cl >= tl && cr <= tr){
if(ff == 0){
return T[node].low;
}
else{
return T[node].mx;
}
}
int mid = (cl + cr) / 2;
ll lef = getval(node * 2, cl, mid, tl, tr, ff);
ll rig = getval(node * 2 + 1, mid + 1, cr, tl, tr, ff);
if(ff == 0)
return min(lef, rig);
else
return max(lef, rig);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v){
int n = c.size();
int q = l.size();
int m = q + 2;
upd(1, 0, m - 1, 0, m - 1, +inf);
upd(1, 0, m - 1, 1, m - 1, -inf);
for(int i = 0 ;i < q; i ++ ){
Q[l[i]].push_back(mp(i + 2, +v[i]));
Q[r[i] + 1].push_back(mp(i + 2, -v[i]));
}
int iq;
int nex;
ll las;
ll fir, bef;
vector<int> soln;
ll xx;
for(int i = 0 ; i < n; i ++ ){
for(auto x : Q[i]){
upd(1, 0, m - 1, x.fi, m - 1, x.se);
}
iq = m - 1;
for(int lg = 18; lg >= 0; lg -- ){
nex = (iq - (1 << lg));
if(nex < 0) continue;
if(getval(1, 0, m - 1, nex, m - 1, 1) - getval(1, 0, m - 1, nex, m - 1, 0) <= c[i]){
iq = nex;
}
}
las = getval(1, 0, m - 1, m - 1, m - 1, 0);
fir = getval(1, 0, m - 1, iq, iq, 0);
bef = getval(1, 0, m - 1, iq - 1, iq - 1, 0);
if(bef > fir){
ll wall_low = getval(1, 0, m - 1, iq, m - 1, 0);
xx = las - wall_low;
}
else{
ll wall_high = getval(1, 0, m - 1, iq, m - 1, 1);
xx = c[i] - (wall_high - las);
}
soln.push_back(xx);
}
return soln;
}
