#include "candies.h"
#include<algorithm>
#include<iostream>
#include <vector>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
vl vec;
const ll inf = 1e18;
ll gmn(int l, int r) {
ll ret = inf;
for (int i = l ; i <= r ; ++ i) ret = min(ret, vec[i]);
return ret;
}
ll gmx(int l, int r) {
ll ret = -inf;
for (int i = l ; i <= r ; ++ i) ret = max(ret, vec[i]);
return ret;
}
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = c.size();
int q = l.size();
vector<int>ans;
for (int i = 0 ; i < n ; ++ i) {
vec = {inf, 0};
for (int j = 0 ; j < q ; ++ j) {
if (l[j] <= i && i <= r[j]) {
vec.emplace_back(vec.back() + v[j]);
}
}
int m = (int)vec.size() - 1;
int l = 0, r = m;
while (l < r) {
int k = (l + r + 1) >> 1;
int mx = gmx(k, m), mn = gmn(k, m);
if (mx - mn >= c[i]) {
l = k;
} else {
r = k - 1;
}
}
ll s;
if (gmx(l, m) == gmx(l + 1, m)) s = gmx(l + 1, m) - c[i];
else s = gmn(l + 1, m);
ans.emplace_back(vec.back() - s);
}
return ans;
}
