#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int>l, std::vector<int> r, std::vector<int> v) {
vector<ll> prefix;
prefix.push_back(v.front());
int n = v.size();
for (int i = 1; i < n; i++) prefix.push_back(v[i] + prefix.back());
vector<ll>min_prefix(n), max_prefix(n);
min_prefix[n - 1] = max_prefix[n - 1] = prefix.back();
for (int i = n - 2; i >= 0; i--)
{
min_prefix[i] = min(min_prefix[i+1], prefix[i]);
max_prefix[i] = max(max_prefix[i + 1], prefix[i]);
}
vector<int> output;
for (int i = 0; i < n; i++)
{
int lower = 0, upper = n - 1, mid;
while (lower < upper)
{
mid = (lower + upper + 1) / 2;
if (max_prefix[mid] - min_prefix[i] >= c[i]) lower = mid;
else upper = mid - 1;
}
if (max_prefix[lower] == max_prefix[lower + 1])
{
output[i] = c[i] - (max_prefix[lower] - prefix.back());
} else {
output[i] = prefix.back() - min_prefix[lower];
}
}
return output;
}
