#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
void dbg(deque<long long>v) {
for(auto z : v)
cout << z << ' ';
cout << '\n';
}
vector<int>distribute_candies(vector<int>c, vector<int>l, vector<int>r, vector<int>V) {
const int n = (int)c.size();
const int m = (int)l.size();
vector<long long>v(m);
for(int i = 0 ; i < m ; i++)
v[i] = (long long)V[i];
vector<long long>value(m+5);
value[0] = 0;
for(int i = 1 ; i <= m ; i++)
value[i] = value[i-1] + v[i-1];
vector<long long>suff_max(m+2), suff_min(m+2);
suff_max[m+1] = LLONG_MIN;
suff_min[m+1] = LLONG_MAX;
for(int i = m ; i >= 0 ; i--) {
suff_max[i] = max(suff_max[i+1], value[i]);
suff_min[i] = min(suff_min[i+1], value[i]);
}
vector<int>ans(n);
for(int i = 0 ; i < n ; i++) {
int p = m+1;
int l = 0, r = m;
while(l <= r) {
int mid = (l+r)/2;
if(suff_max[mid] - suff_min[mid] > c[i]) {
l = mid+1, p = mid;
} else {
r = mid-1;
}
}
//cout << p << '\n';
if(p == m+1) {
ans[i] = value[m] - suff_min[0];
continue;
}
if(value[p] == suff_min[p]) { // smaller side
ans[i] = max(c[i] - (suff_max[p] - value[m]), 0LL);
} else {
ans[i] = max(value[m] - suff_min[p], 0LL);
}
}
return ans;
}
