#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(0);
int n = v.size();
for (int i = 0; i < n; i++) prefix.push_back(v[i] + prefix.back());
vector<ll>min_prefix(n+1), max_prefix(n+1);
min_prefix[n] = max_prefix[n] = prefix.back();
for (int i = n - 1; i >= 0; i--)
{
min_prefix[i] = min(min_prefix[i+1], prefix[i]);
max_prefix[i] = max(max_prefix[i + 1], prefix[i]);
}
// for (int i : prefix) cout << i << " ";
// cout << "\n";
// for (int i : min_prefix) cout << i << " ";
// cout << "\n";
// for (int i : max_prefix) cout << i << " ";
// cout << "\n";
n = c.size();
vector<int> output(n);
for (int i = 0; i < n; i++)
{
int lower = -1, upper = v.size(), mid;
while (lower < upper)
{
mid = (lower + upper + 1) / 2;
if (max_prefix[mid] - min_prefix[mid] >= c[i]) lower = mid;
else upper = mid - 1;
}
if (lower == -1) {
output[i] = prefix.back();
continue;
}
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;
}
/*
1 4 -3 6 7 -5
1 5 2 8 15 10
1 2 2 8 10 10
15 15 15 15 15 10
c = 8 -> 3
*/
