#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Neoud {
int mini = 0, maxi = 0;
int pos_min = -1, pos_max = -1;
};
struct Ret {
bool type;
int val;
int pos;
};
struct Segtree {
vector<Neoud> valeurs;
vector<int> lazy;
int taille = 1;
Segtree(int n) {
while(taille < n) {
taille <<= 1;
}
valeurs.resize(2*taille);
lazy.resize(2*taille, 0);
for (int i = 0; i < taille; i++)
{
valeurs[taille + i].pos_min = i;
valeurs[taille + i].pos_max = i;
}
for (int i = taille - 1; i >= 0; i--)
{
valeurs[i].pos_min = max(valeurs[2*i].pos_min, valeurs[2*i+1].pos_min);
valeurs[i].pos_max = max(valeurs[2*i].pos_max, valeurs[2*i+1].pos_max);
}
}
void push(int pos) {
if (pos < taille) {
lazy[2*pos] += lazy[pos];
valeurs[2*pos].mini += lazy[pos];
valeurs[2*pos].maxi += lazy[pos];
lazy[2*pos+1] += lazy[pos];
valeurs[2*pos+1].mini += lazy[pos];
valeurs[2*pos+1].maxi += lazy[pos];
}
lazy[pos] = 0;
}
int req_point(int pos) {
point(taille + pos);
return valeurs[taille + pos].mini;
}
void point(int pos) {
if (pos != 1)
{
point(pos/2);
}
push(pos);
}
void update(int pos, int lr, int l, int r, int val) {
push(pos);
if (r <= lr) {
return;
}
if (l >= lr) {
lazy[pos] += val;
valeurs[pos].mini += val;
valeurs[pos].maxi += val;
return;
}
update(2*pos, lr, l, (l+r)/2, val);
update(2*pos + 1, lr, (l+r)/2, r, val);
valeurs[pos].mini = min(valeurs[2*pos].mini, valeurs[2*pos+1].mini);
if (valeurs[pos].mini == valeurs[2*pos+1].mini) {
valeurs[pos].pos_min = valeurs[2*pos+1].pos_min;
}
else {
valeurs[pos].pos_min = valeurs[2*pos].pos_min;
}
valeurs[pos].maxi = max(valeurs[2*pos].maxi, valeurs[2*pos+1].maxi);
if (valeurs[pos].maxi == valeurs[2*pos+1].maxi) {
valeurs[pos].pos_max = valeurs[2*pos+1].pos_max;
}
else {
valeurs[pos].pos_max = valeurs[2*pos].pos_max;
}
}
Ret requete(int pos, int mini, int maxi, int cible) {
push(pos);
if (pos >= taille) {
if (valeurs[pos].mini < mini && max(maxi, valeurs[pos].maxi) - min(mini, valeurs[pos].mini) >= cible) {
maxi = max(maxi, valeurs[pos].maxi);
return (Ret){true, maxi, pos-taille};
}
else {
mini = min(mini, valeurs[pos].mini);
return (Ret){false, mini, pos-taille};
}
}
int min2 = min(mini, valeurs[2*pos+1].mini);
int max2 = max(maxi, valeurs[2*pos+1].maxi);
if (max2 - min2 > cible) {
return requete(2*pos+1, mini, maxi, cible);
}
else {
Ret r = requete(2*pos, min2, max2, cible);
if (r.type) {
if (valeurs[2*pos+1].maxi == r.val) {
r.pos = valeurs[2*pos+1].pos_max;
}
}
else {
if (valeurs[2*pos+1].mini == r.val) {
r.pos = valeurs[2*pos+1].pos_min;
}
}
return r;
}
}
};
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());
int i_inter = 0;
vector<signed> rep(n, 0);
Segtree segtree(q+2);
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];
}
segtree.update(1, j+1, 0, segtree.taille, val);
i_inter++;
}
Ret r = segtree.requete(1, 1e18, -1e18, c[i]);
int pos = r.pos;
if (pos == 0) {
rep[i] = segtree.req_point(q);
}
else if (r.type) {
rep[i] = c[i] - (segtree.req_point(pos) - segtree.req_point(q));
}
else {
rep[i] = segtree.req_point(q) - segtree.req_point(pos);
}
}
return rep;
}
