#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int cap;
vector<pair<ll, int>> Smi, Sma;
vector<ll> O;
void apply(ll v, int i){
Smi[i].first += v;
Sma[i].first += v;
O[i] += v;
}
void push(int i){
if(O[i] != 0){
apply(O[i], 2*i);
apply(O[i], 2*i+1);
O[i] = 0;
}
}
void add(int l, int r, ll v, int a, int b, int i){
if(l <= a && b <= r) apply(v, i);
else if(b < l || r < a) return;
else{
push(i);
int m = (a+b)/2;
add(l, r, v, a, m, 2*i);
add(l, r, v, m+1, b, 2*i+1);
Smi[i] = min(Smi[2*i], Smi[2*i+1]);
Sma[i] = max(Sma[2*i], Sma[2*i+1]);
}
}
pair<ll, int> qryMi(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return Smi[i];
else if(b < l || r < a) return {INF, 0};
push(i);
int m = (a+b)/2;
return min(qryMi(l, r, a, m, 2*i), qryMi(l, r, m+1, b, 2*i+1));
}
pair<ll, int> qryMa(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return Sma[i];
else if(b < l || r < a) return {-INF, 0};
push(i);
int m = (a+b)/2;
return max(qryMa(l, r, a, m, 2*i), qryMa(l, r, m+1, b, 2*i+1));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = (int)c.size();
int q = (int)l.size();
for(cap = 1; cap <= q; cap *= 2);
Smi.assign(2*cap, {0, 0});
Sma.assign(2*cap, {0, q});
O.assign(2*cap, 0);
for(int i = 0; i < cap; i++) Smi[i+cap].second = Sma[i+cap].second = i;
for(int i = q+1; i < cap; i++) Smi[i+cap].first = INF, Sma[i+cap].first = -INF;
vector<vector<pair<int, int>>> todo(n+1);
for(int i = 0; i < q; i++){
todo[l[i]].emplace_back(i, 1);
todo[r[i]+1].emplace_back(i, -1);
}
vector<int> ans(n);
for(int i = 0; i < n; i++){
for(auto [j, op] : todo[i]){
add(j+2, q+1, v[j]*op, 1, cap, 1);
}
int lo = 1, hi = q+1;
for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
if(qryMa(mid, q+1, 1, cap, 1).first - qryMi(mid, q+1, 1, cap, 1).first <= c[i]) hi = mid;
else lo = mid+1;
}
lo--;
auto mi = qryMi(lo, q+1, 1, cap, 1);
auto ma = qryMa(lo, q+1, 1, cap, 1);
ll cur = qryMi(q+1, q+1, 1, cap, 1).first;
// cerr << cur << " " << mi.second << " " << ma.second << "\n";
if(ma.first-mi.first > c[i]){
if(mi.second < ma.second) ans[i] = int(cur-ma.first+c[i]);
else ans[i] = int(cur-mi.first);
}
else{
ans[i] = int(cur-mi.first);
}
}
return ans;
}
