#include "candies.h"
#include<algorithm>
#include<iostream>
#include <vector>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
const int N = 1e6 + 123;
const ll inf = 1e18;
ll tmn[N << 2], tmx[N << 2];
ll p[N << 2];
int n, q;
void push(int v, int l, int r) {
if (!p[v]) return;
tmn[v] += p[v], tmx[v] += p[v];
if (r - l > 1) p[v << 1] += p[v], p[v<<1|1] += p[v];
p[v] = 0;
}
void upd1(int L, int R, ll val, int l = 0, int r = q + 1, int v = 1) {
push(v, l, r);
if (L <= l && r <= R) {
p[v] += val;
push(v, l, r);
return;
}
if (L >= r || l >= R) return;
int m = (l + r) >> 1;
upd1(L, R, val, l, m, v << 1);
upd1(L, R, val, m, r, v<<1|1);
tmn[v] = min(tmn[v << 1], tmn[v<<1|1]);
tmx[v] = max(tmx[v << 1], tmx[v<<1|1]);
}
ll gmn1(int L, int R, int l = 0, int r = q + 1, int v = 1) {
push(v, l, r);
if (L <= l && r <= R) return tmn[v];
if (L >= r || l >= R) return inf;
int m = (l + r) >> 1;
return min(gmn1(L, R, l, m, v << 1), gmn1(L, R, m, r, v<<1|1));
}
ll gmx1(int L, int R, int l = 0, int r = q + 1, int v = 1) {
push(v, l, r);
if (L <= l && r <= R) return tmx[v];
if (L >= r || l >= R) return -inf;
int m = (l + r) >> 1;
return max(gmx1(L, R, l, m, v << 1), gmx1(L, R, m, r, v<<1|1));
}
void upd(int l, int r, ll val) {
upd1(l + 1, r + 1, val);
}
ll gmn(int l, int r) { return gmn1(l, r + 1); }
ll gmx(int l, int r) { return gmx1(l, r + 1); }
vector<int>ev[N];
vi distribute_candies(vi c, vi l, vi r, vi v) {
n = c.size();
q = l.size();
vector<int>ans;
for (int i = 0 ; i < q ; ++ i) ev[l[i]].emplace_back(i), ev[r[i]+1].emplace_back(i);
for (int i = 0 ; i < n ; ++ i) {
//cout << " ---\n" << i << "\n-\n";
for (int j : ev[i]) {
if (l[j] == i) {
//cout << "adding " << j << " " << v[j] << endl;
upd(j, q, +v[j]);
} else {
//cout << "deleting " << j << " " << v[j] << endl;
upd(j, q, -v[j]);
}
}
int l = 0, r = q - 1;
int o = -1;
while (l <= r) {
int k = (l + r) >> 1;
ll mx = gmx(k, q), mn = gmn(k, q);
//cout << k << " " << mx << " " << mn << endl;
if (mx - mn >= c[i]) {
l = k + 1;
o = k;
} else {
r = k - 1;
}
}
if (o == -1) {
//cout << i << " e\n";
ans.emplace_back(gmx(q, q) - gmn(0, q));
continue;
}
ll s;
if (gmx(o, q) == gmx(o + 1, q)) s = gmx(o + 1, q) - c[i];
else s = gmn(o + 1, q);
//cout << i << " " << o << " " << s << endl;
ans.emplace_back(gmx(q, q) - s);
}
return ans;
}
