#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>
#define INF (1ll<<60)
#define MAX 200000
//para el pll de last
#define p first
#define in second
//para el sweepline
#define p_arbol first
#define tipo second
struct x {
lli g_v;
lli g_id;
lli ch_v;
lli ch_id;
lli dif;
lli lazy;
lli sum;
};
lli n,offset;
x stree[MAX*4];
x trash = {-INF,0,INF,0,0,0,0};
vector<int> res,valor;
vector<pll> spline[MAX+2];
void push(lli pos) { //correcto
if (stree[pos].lazy == 0) return;
stree[pos].ch_v += stree[pos].lazy;
stree[pos].g_v += stree[pos].lazy;
if (pos < offset) {
stree[pos*2].lazy += stree[pos].lazy;
stree[pos*2+1].lazy += stree[pos].lazy;
}
stree[pos].lazy = 0;
return;
}
x mergea(x izq, x der){ //revisado
if (izq.ch_v < der.ch_v) {
der.ch_v = izq.ch_v;
der.ch_id = izq.ch_id;
}
if (izq.g_v > der.g_v) {
der.g_v = izq.g_v;
der.g_id = izq.g_id;
}
der.sum += izq.sum;
der.dif = der.g_v - der.ch_v;
return der;
}
x query(lli pos, lli ini, lli fin, lli l, lli r) { //correcto
if (l > r) trash;
push(pos);
if (ini > r || fin < l) return trash;
if (l <= ini && fin <= r) return stree[pos];
lli mitad = (ini+fin)/2;
x a = query(pos*2,ini,mitad,l,r);
x b = query(pos*2+1,mitad+1,fin,l,r);
return mergea(a,b);
}
void pushea(lli pos, lli ini, lli fin, lli l, lli r, lli pp) {
if (l > r) return;
push(pos);
if (ini > r || fin < l) return;
if (l <= ini && fin <= r) {
stree[pos].lazy = pp;
push(pos);
return;
}
lli mitad = (ini+fin)/2;
pushea(pos*2,ini,mitad,l,r,pp);
pushea(pos*2+1,mitad+1,fin,l,r,pp);
stree[pos] = mergea(stree[pos*2], stree[pos*2+1]);
}
void update(lli pos, lli s) {
while (pos > 0) {
stree[pos].sum += s;
pos /= 2;
}
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> VA) {
swap(valor,VA);
n = valor.size();
offset = 1;
while (offset < (n+1)) offset *= 2;
rep(i,0,n-1) {
spline[l[i]].push_back({i,1});
spline[r[i]+1].push_back({i,0});
}
rep(i,0,offset-1) stree[offset+i] = {0,i,0,i,0,0,0};
repa(i,offset-1,1) stree[i] = mergea(stree[i*2], stree[i*2+1]);
res.resize(c.size());
rep(i,0,c.size()-1) {
//actualizo mi arbol
for (auto act : spline[i]) {
act.p_arbol++;
if (act.tipo == 1) {
pushea(1,0,offset-1,act.p_arbol,offset-1,valor[act.p_arbol-1]);
update(offset+act.p_arbol,valor[act.p_arbol-1]);
}
else {
pushea(1,0,offset-1,act.p_arbol,offset-1,-valor[act.p_arbol-1]);
update(offset+act.p_arbol,-valor[act.p_arbol-1]);
}
}
//rep(i,1,7) {
// debugsl(i);
// debugsl(stree[i].g_v);
// debugsl(stree[i].g_id);
// debugsl(stree[i].ch_v);
// debugsl(stree[i].ch_id);
// debug(stree[i].sum);
//}
lli act = c[i];
lli ini = 0;
lli mitad,fin = n;
pll last = {-1,0};
while (ini <= fin) {
mitad = (ini+fin)/2;
x w = query(1,0,offset-1,mitad,offset-1);
//debugsl(mitad);
//debugsl(w.dif);
//debugsl(w.g_v);
//debug(w.ch_v);
if(w.dif >= act) {
//debugsl(w.g_id);
//debug(w.ch_id);
if (w.g_id > w.ch_id) {
last.in = act;
last.p = w.g_id;
}
else {
last.p = w.ch_id;
last.in = 0;
}
ini = mitad+1;
}
else fin = mitad - 1;
}
//debugsl(last.p);
//debug(last.in);
//cout << endl;
if (last.p < 0) {
last.p = stree[1].ch_id;
last.in = 0;
}
res[i] = last.in + stree[1].sum;
res[i] -= query(1,0,offset-1,0,last.p).sum;
}
return res;
}
