#include "candies.h"
#include<algorithm>
#include<iostream>
#include <vector>
using namespace std;
using vi = vector<int>;
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = c.size();
int q = l.size();
vector<int>ans;
vector<int>vec;
for (int i = 0 ; i < n ; ++ i) {
vec = {0, 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 = 1, r = m;
while (l < r) {
int k = (l + r) >> 1;
int mx = -1, mn = c[i] + 1;
for (int j = k ; j <= m ; ++ j) {
mx = max(mx, vec[j]);
mn = min(mn, vec[j]);
}
if (mx - mn > c[i]) {
l = k + 1;
} else {
r = k;
}
}
int s;
if (vec[r] > vec[r - 1]) s = vec[r] - c[i];
else s = vec[r];
ans.emplace_back(vec.back() - s);
}
return ans;
}
