#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
long long mins[(1 << 19)];
long long maxs[(1 << 19)];
long long decs[(1 << 19)];
void ajoute(int deb, int fin, long long val, int n = 1, int d = 0, int f = (1 << 18)) {
if(deb >= f || fin <= d) return;
if(deb <= d && f <= fin) {
decs[n] += val;
return;
}
int m = (d + f) / 2;
ajoute(deb, fin, val, 2 * n, d, m);
ajoute(deb, fin, val, 2 * n + 1, m, f);
mins[n] = min(mins[2 * n] + decs[2 * n], mins[2 * n + 1] + decs[2 * n + 1]);
maxs[n] = max(maxs[2 * n] + decs[2 * n], maxs[2 * n + 1] + decs[2 * n + 1]);
}
long long min_entre(int deb, int fin, int n = 1, int d = 0, int f = (1 << 18)) {
if(deb >= f || fin <= d) return 1e18;
if(deb <= d && f <= fin) {
return mins[n] + decs[n];
}
int m = (d + f) / 2;
return min(min_entre(deb, fin, 2 * n, d, m), min_entre(deb, fin, 2 * n + 1, m, f)) + decs[n];
}
long long max_entre(int deb, int fin, int n = 1, int d = 0, int f = (1 << 18)) {
if(deb >= f || fin <= d) return -1e18;
if(deb <= d && f <= fin) {
return maxs[n] + decs[n];
}
int m = (d + f) / 2;
return max(max_entre(deb, fin, 2 * n, d, m), max_entre(deb, fin, 2 * n + 1, m, f)) + decs[n];
}
int prem_sup_borne(int borne, int n = 1, int sz = (1 << 18), long long shift = 0, long long mini = 1e18, long long maxi = -1e18) {
if(sz == 1) {
return 0;
}
shift += decs[n];
long long maxim = max(maxi, maxs[2 * n + 1] + decs[2 * n + 1] + shift);
long long minim = min(mini, mins[2 * n + 1] + decs[2 * n + 1] + shift);
if(maxim - minim >= borne) return sz / 2 + prem_sup_borne(borne, 2 * n + 1, sz / 2, shift, mini, maxi);
return prem_sup_borne(borne, 2 * n, sz / 2, shift, minim, maxim);
}
vector<int> distribute_candies(vector<int> bornes, vector<int> debs, vector<int> fins, vector<int> ajouts) {
vector<int> final(bornes.size(), -1);
vector<vector<int>> intersDeb(bornes.size());
vector<vector<int>> intersFin(bornes.size());
for(int iReq = 0;iReq < (int)ajouts.size();iReq++) {
intersDeb[debs[iReq]].push_back(iReq);
intersFin[fins[iReq]].push_back(iReq);
}
int LAST = ajouts.size() + 2;
long long total = 0;
for(int pos = 0;pos < (int)bornes.size();pos++) {
for(int iReq : intersDeb[pos]) {
ajoute(iReq + 1, (1 << 18), ajouts[iReq]);
total += ajouts[iReq];
}
int premFail = prem_sup_borne(bornes[pos]);
if(max_entre(premFail, LAST) - min_entre(premFail, LAST) < bornes[pos]) premFail = LAST;
if(max_entre(premFail, LAST) == max_entre(premFail, premFail + 1) || premFail == LAST) {
if(premFail == LAST) premFail = 0;
long long minApres = min_entre(premFail, LAST + 1);
final[pos] = total - minApres;
} else {
long long maxApres = max_entre(premFail, LAST + 1);
final[pos] = bornes[pos] - (maxApres - total);
}
for(int iReq : intersFin[pos]) {
ajoute(iReq + 1, (1 << 18), -ajouts[iReq]);
total -= ajouts[iReq];
}
}
return final;
}
