#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
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>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+1), suff_min(m+1);
suff_max[m] = LLONG_MIN;
suff_min[m] = LLONG_MAX;
for(int i = m-1 ; i >= 0 ; i--) {
suff_max[i] = max(suff_max[i+1], value[i+1]);
suff_min[i] = min(suff_min[i+1], value[i+1]);
}
vector<int>ans(n);
for(int i = 0 ; i < n ; i++) {
int p = m;
int l = 0, r = m-1;
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;
}
}
if(p == m) {
ans[i] = value[m];
continue;
}
if(value[p+1] == 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);
}
assert(ans[i] <= c[i]);
}
return ans;
}
