#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<signed> distribute_candies(vector<signed> c, vector<signed> l, vector<signed> r, vector<signed> v) {
int n = c.size();
int q = l.size();
vector<pair<int,int>> inter;
for (int i = 0; i < q; i++)
{
inter.push_back(make_pair(l[i], i));
inter.push_back(make_pair(r[i]+1, i));
}
sort(inter.begin(), inter.end());
vector<int> hauteurs(q+1, 0);
int i_inter = 0;
vector<signed> rep(n, 0);
for (int i = 0; i < n; i++)
{
while(i_inter < (int)inter.size() && inter[i_inter].first <= i) {
int val = 0;
int j = inter[i_inter].second;
if (inter[i_inter].first == l[j]) {
val = v[j];
}
else {
val = -v[j];
}
for (int k = j; k <= q; k++)
{
hauteurs[k] += val;
}
i_inter++;
}
int mini = 1e9;
int maxi = -1e9;
int pos_min = -1;
int pos_max = -1;
int pos = -1;
for (int j = q - 1; j >= 0; j--)
{
if (hauteurs[j] < mini) {
mini = hauteurs[j];
pos_min = j;
}
if (hauteurs[j] > maxi) {
maxi = hauteurs[j];
pos_max = j;
}
if (maxi - mini >= c[i]) {
if (j == pos_min) {
pos = pos_max;
}
else {
pos = pos_min;
}
break;
}
}
if (pos == -1) {
if (mini >= 0 && maxi <= c[i]) {
rep[i] = hauteurs[q];
pos = -2;
}
else if (mini < 0) {
pos = pos_min;
}
else if (maxi > c[i]) {
pos = pos_max;
}
}
if (pos == pos_max) {
rep[i] = c[i] - (hauteurs[pos] - hauteurs[q]);
}
else {
rep[i] = hauteurs[q] - hauteurs[pos];
}
}
return rep;
}
