#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int NMAX = 100000;
#define int long long
const int INFINI = 1000000000000ll;
struct T {
int poid, normal, enPair;
T(int prem = 0, int a = 0, int b = 0)
{
poid = prem;
normal = a;
enPair = b;
}
bool operator<(const T &other) const {
return poid < other.poid;
}
};
vector<pair<int, pair<int, int>>> aretes;
int boss[NMAX];
int minRouge[NMAX], minNoir[NMAX];
T infos[NMAX];//W, A, B
int sommeB[NMAX];
int sommeTotal;
int taille[NMAX];
int sommeComposante[NMAX];
int findBoss(int noeud)
{
if(boss[noeud] == noeud)
{
return noeud;
}
return boss[noeud] = findBoss(boss[noeud]);
}
void comparerBalance(int noeud)
{
minRouge[findBoss(noeud)] = min(minRouge[findBoss(noeud)], (infos[noeud].normal-infos[noeud].enPair));
minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], (infos[noeud].normal-infos[noeud].enPair));
}
void faire(int bossA, int bossB, bool inverserCouleur)
{
if(inverserCouleur)
{
minRouge[bossA] = min(minRouge[bossA], minNoir[bossB]);
minNoir[bossA] = min(minNoir[bossA], minRouge[bossB]);
}
else
{
minRouge[bossA] = min(minRouge[bossA], minRouge[bossB]);
minNoir[bossA] = min(minNoir[bossA], minNoir[bossB]);
}
}
void merge(int a, int b)
{
int bossA = findBoss(a), bossB = findBoss(b);
if(bossA == bossB)
{
int balance = a+1;
comparerBalance(balance);
sommeTotal -= sommeComposante[bossA];
}
else
{
int debutB = bossB%2;
int debutA = bossA%2;
int finA = (debutA + taille[bossA]-1)%2;
if(finA == debutB)
faire(bossA, bossB, 1);
else
{
faire(bossA, bossB, 0);
}
sommeB[bossA] += sommeB[bossB];
taille[bossA] += taille[bossB];
sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
boss[bossB] = bossA;
}
int noeud = bossA;
if(taille[noeud]%2 == 0)
{
sommeComposante[noeud] = sommeB[noeud];
}
else if(bossA%2 == 0)
{
sommeComposante[noeud] = sommeB[noeud]+minRouge[noeud];
}
else
{
sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud];
}
sommeTotal += sommeComposante[noeud];
}
pair<int, int> requetes[NMAX];
#undef int
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
#define int long long
sommeTotal = 0;
int Q = (int)E.size();
int N = W.size();
for(int i = 0; i < Q; i++)
{
requetes[i] = {E[i], i};
}
sort(requetes, requetes+Q);
for(int i = 0; i < N; i++)
{
infos[i] = {W[i], A[i], B[i]};
}
sort(infos, infos+N);
for(int i = 1; i < N; i++)
{
aretes.push_back({2*(infos[i].poid-infos[i-1].poid), pair<int, int>(i-1, i)});
if(i >= 2)
aretes.push_back({2*(infos[i].poid-infos[i-2].poid)+1, pair<int, int>(i-2, i)});
}
sort(aretes.begin(), aretes.end());
//aVoir
for(int i = 0; i < N; i++)
{
boss[i] = i;
taille[i] = 1;
sommeTotal += infos[i].normal;
sommeB[i] = infos[i].enPair;
sommeComposante[i] = infos[i].normal;
if(i % 2 == 0)
{
minRouge[i] = (infos[i].normal - infos[i].enPair);
minNoir[i] = INFINI;
}
else
{
minNoir[i] = (infos[i].normal- infos[i].enPair);
minRouge[i] = INFINI;
}
}
std::vector<long long> R(Q);
int iEnlever = 0;
for(int i = 0; i < Q; i++)
{
int D = requetes[i].first;
while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= 2 * D + 1))
{
merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
iEnlever++;
}
R[requetes[i].second] = sommeTotal;
}
return R;
}
/** */
