#include "nile.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 2e17;
const int MAX = 1e5+42;
struct Requ {
int requete, id;
bool operator< (Requ other) {
return requete < other.requete;
}
};
struct Comp {
int pere, cout, minPair, minImpair, minSaut, taille, iPremier;
bool operator< (Comp other) {
return taille < other.taille;
}
};
struct Dist {
int ecart, id, type;
bool operator< (Dist other) {
return ecart < other.ecart;
}
};
struct Reli {
int poids, coutSeul, coutDeux, diffCout;
bool operator< (Reli other) {
return poids < other.poids;
}
};
vector<Reli> relique;
vector<Requ> requete;
vector<Comp> composante(MAX);
vector<Dist> dist;
vector<int> answer;
vector<int> fils[MAX];
int sommeTotal = 0;
void merge(Dist arete) {
int nodeA = composante[arete.id].pere;
int nodeB = composante[arete.id + 1].pere;
if(composante[nodeA] < composante[nodeB]) {
swap(nodeA, nodeB);
}
for(int loop = 0; loop < fils[nodeB].size(); ++loop) {
composante[fils[nodeB][loop]].pere = nodeA;
fils[nodeA].push_back(fils[nodeB][loop]);
}
composante[nodeA].taille = fils[nodeA].size();
composante[nodeB].taille = 0;
fils[nodeB].clear();
composante[nodeA].iPremier = min(composante[nodeA].iPremier, composante[nodeB].iPremier);
composante[nodeA].minImpair = min(composante[nodeA].minImpair, composante[nodeB].minImpair);
composante[nodeA].minPair = min(composante[nodeA].minPair, composante[nodeB].minPair);
composante[nodeA].minSaut = min(composante[nodeA].minSaut, composante[nodeB].minSaut);
sommeTotal -= composante[nodeA].cout + composante[nodeB].cout;
if(composante[nodeA].taille % 2 == 0) {
composante[nodeA].cout = 0;
}
else {
int coutMin = composante[nodeA].minSaut;
if(composante[nodeA].iPremier % 2 == 0) {
composante[nodeA].cout = min(coutMin, composante[nodeA].minPair);
}
else {
composante[nodeA].cout = min(coutMin, composante[nodeA].minImpair);
}
}
sommeTotal += composante[nodeA].cout;
}
void update(Dist arete) {
int node = composante[arete.id].pere;
composante[node].minSaut = min(composante[node].minSaut, relique[arete.id].diffCout);
sommeTotal -= composante[node].cout;
composante[node].cout = min(composante[node].cout, composante[node].minSaut);
sommeTotal += composante[node].cout;
}
#undef int long long
vector<long long> calculate_costs(vector<int> poids, vector<int> coutSeul, vector<int> coutDeux, vector<int> E) {
int n = poids.size();
for(int loop = 0; loop < n; ++loop) {
relique.push_back({poids[loop], coutSeul[loop], coutDeux[loop], coutSeul[loop] - coutDeux[loop]});
}
sort(relique.begin(), relique.end());
int q = E.size();
for(int loop = 0; loop < q; ++loop) {
answer.push_back(0);
requete.push_back({0, 0});
}
for(int loop = 0; loop < q; ++loop) {
requete[loop] = {E[loop], loop};
}
sort(requete.begin(), requete.end());
for(int loop = 0; loop < n; ++loop) {
composante[loop].pere = loop;
composante[loop].cout = relique[loop].diffCout;
composante[loop].minSaut = INF;
composante[loop].taille = 1;
composante[loop].iPremier = loop;
if(loop % 2 == 0) {
composante[loop].minPair = relique[loop].diffCout;
composante[loop].minImpair = INF;
}
else {
composante[loop].minPair = INF;
composante[loop].minImpair = relique[loop].diffCout;
}
}
for(int loop = 0; loop < n-1; ++loop) {
dist.push_back({relique[loop+1].poids - relique[loop].poids, loop, 1});
}
for(int loop = 0; loop < n-2; ++loop) {
dist.push_back({relique[loop+2].poids - relique[loop].poids, loop+1, 2});
}
dist.push_back({INF, -1, -1});
sort(dist.begin(), dist.end());
for(int loop = 0; loop < n; ++loop) {
fils[loop].push_back(loop);
}
for(int loop = 0; loop < n; ++loop) {
sommeTotal += relique[loop].coutSeul;
}
int iEcart = 0;
for(int loop = 0; loop < q; ++loop) {
while(dist[iEcart].ecart <= requete[loop].requete) {
if(dist[iEcart].type == 1) {
merge(dist[iEcart]);
}
else {
update(dist[iEcart]);
}
iEcart++;
}
answer[requete[loop].id] = sommeTotal;
}
return answer;
}
