#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct relique{
int p,cout1,pere;
bool operator< (relique other){
return p<other.p;
}
};
struct quest{
int q,numquest;
bool operator< (quest other){
return q<other.q;
}
};
struct compo{
int pere,premier,dernier,minpair,minimpair,minponts,prix;
};
struct dist{
int d,premier;
bool operator< (dist other){
return d<other.d;
}
};
const int INFINI=1000ll*1000*1000*1000*1000*1000ll+2,QUESTMAXI=100*1000+2;
vector<relique> reliques;
vector<quest> questions;
vector<compo> composantes;
int nbreliques,ajout;
vector<dist> aretes;
vector<dist> ponts2;
int reponse[QUESTMAXI];
vector<int> r;
int trouver(int numc){
if (composantes[numc].pere!=numc){
return composantes[numc].pere=trouver(composantes[numc].pere);
}
return numc;
}
void unir(int compo1,int compo2){
compo1=trouver(compo1);
compo2=trouver(compo2);
ajout-=composantes[compo1].prix+composantes[compo2].prix;
composantes[compo2].pere=compo1;
compo nouv;
nouv.pere=compo1;
nouv.premier=min(composantes[compo1].premier,composantes[compo2].premier);
nouv.dernier=max(composantes[compo1].dernier,composantes[compo2].dernier);
nouv.minpair=min(composantes[compo1].minpair,composantes[compo2].minpair);
nouv.minimpair=min(composantes[compo1].minimpair,composantes[compo2].minimpair);
nouv.minponts=min(composantes[compo1].minponts,composantes[compo2].minponts);
if ((nouv.dernier-nouv.premier)%2==1){
nouv.prix=0;
}
else {
if (nouv.premier%2==0){
nouv.prix=min(nouv.minpair,nouv.minponts);
}
else {
nouv.prix=min(nouv.minimpair,nouv.minponts);
}
}
composantes[compo1]=nouv;
ajout+=nouv.prix;
}
#undef int
vector<long long> calculate_costs(vector<int> poids, vector<int> seul, vector<int> deux, vector<int> requetes) {
#define int long long
nbreliques=(int)poids.size();
for (int irelique=0;irelique<nbreliques;irelique++){
relique rel;
ajout+=deux[irelique];
rel.p=poids[irelique];
rel.cout1=seul[irelique]-deux[irelique];
rel.pere=0;
reliques.push_back(rel);
}
sort(reliques.begin(),reliques.end());
for (int irelique=0;irelique<nbreliques;irelique++){
reliques[irelique].pere=irelique;
}
for (int iquest=0;iquest<(int)requetes.size();iquest++){
quest qu;
qu.q=requetes[iquest];
qu.numquest=iquest;
questions.push_back(qu);
}
sort(questions.begin(),questions.end());
for (int irelique=0;irelique<nbreliques;irelique++){
compo c;
if (irelique%2==0){
c={irelique,irelique,irelique,reliques[irelique].cout1,INFINI,INFINI,reliques[irelique].cout1};
}
else {
c={irelique,irelique,irelique,INFINI,reliques[irelique].cout1,INFINI,reliques[irelique].cout1};
}
ajout+=reliques[irelique].cout1;
composantes.push_back(c);
}
for (int irelique=0;irelique<nbreliques-1;irelique++){
dist ar;
ar={reliques[irelique+1].p-reliques[irelique].p,irelique};
aretes.push_back(ar);
}
sort(aretes.begin(),aretes.end());
for (int irelique=0;irelique<nbreliques-2;irelique++){
dist ar;
ar={reliques[irelique+2].p-reliques[irelique].p,irelique};
ponts2.push_back(ar);
}
sort(ponts2.begin(),ponts2.end());
int arec=0,pontec=0;
for (auto qec:questions){
while (arec<nbreliques-1 and aretes[arec].d<=qec.q){
unir(aretes[arec].premier,aretes[arec].premier+1);
arec++;
}
while (pontec<nbreliques-2 and ponts2[pontec].d<=qec.q){
composantes[trouver(ponts2[pontec].premier+1)].minponts=min(composantes[trouver(ponts2[pontec].premier+1)].minponts,
reliques[ponts2[pontec].premier+1].cout1);
ajout-=composantes[trouver(ponts2[pontec].premier+1)].prix;
composantes[trouver(ponts2[pontec].premier+1)].prix=min(composantes[trouver(ponts2[pontec].premier+1)].prix,
composantes[trouver(ponts2[pontec].premier+1)].minponts);
ajout+=composantes[trouver(ponts2[pontec].premier+1)].prix;
pontec++;
}
reponse[qec.numquest]=ajout;
}
for (int irep=0;irep<(int)requetes.size();irep++){
r.push_back(reponse[irep]);
}
return r;
}
