#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;
const ll INF = 1e18; // Dostatečně velké nekonečno
struct Artifact {
int id;
int w;
ll diff; // Penalizace (A - B)
};
struct Event {
int w; // Váha (threshold)
int type; // 1: Sousedé (i, i+1), 2: Skok (i, i+2), 3: Dotaz
int idx; // Index
// Řazení: primárně podle váhy, sekundárně typ (hrany dříve než dotazy)
bool operator<(const Event& other) const {
if (w != other.w) return w < other.w;
return type < other.type;
}
};
struct DSU {
vector<int> parent;
vector<int> sz; // Velikost komponenty
vector<int> min_idx; // Nejnižší globální index v komponentě (určuje paritu majority)
// min_diff[0]: Nejmenší penalizace (A-B) pro globálně SUDÝ prvek v této komponentě
// min_diff[1]: Nejmenší penalizace (A-B) pro globálně LICHÝ prvek v této komponentě
vector<ll> min_diff[2];
// min_jump_diff[0]: Nejmenší penalizace SUDÉHO prvku, který je "přeskočen" aktivním skokem
// min_jump_diff[1]: Nejmenší penalizace LICHÉHO prvku, který je "přeskočen" aktivním skokem
vector<ll> min_jump_diff[2];
ll current_total_penalty = 0;
DSU(int n, const vector<Artifact>& arts) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
sz.assign(n, 1);
min_idx.resize(n);
min_diff[0].assign(n, INF);
min_diff[1].assign(n, INF);
min_jump_diff[0].assign(n, INF);
min_jump_diff[1].assign(n, INF);
for(int i=0; i<n; ++i) {
min_idx[i] = i;
min_diff[i%2][i] = arts[i].diff;
// Na začátku je každý sám -> lichá komponenta -> platí penalizaci
current_total_penalty += arts[i].diff;
}
}
// Find s kompresí cesty
int find(int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
// Výpočet penalizace pro jednu komponentu
ll get_penalty(int root) {
// Pokud je komponenta sudá, všichni se spárují -> penále 0
if (sz[root] % 2 == 0) return 0;
// Komponenta je lichá -> jeden musí zůstat sám (zaplatí A-B)
// Která parita je "většinová"? Ta, kterou má začátek komponenty (min_idx).
int major_parity = min_idx[root] % 2;
int minor_parity = 1 - major_parity;
// Základní možnost: Obětujeme nejlevnějšího z majority
ll cost = min_diff[major_parity][root];
// Možnost skoku: Obětujeme někoho z minority, ALE jen pokud byl "přeskočen"
// (Tj. existuje aktivní skok přes něj)
cost = min(cost, min_jump_diff[minor_parity][root]);
return cost;
}
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
// OPTIMALIZACE: Union by Size (připojujeme menší k většímu)
// Toto je kritické proti TLE
if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
// 1. Odečteme staré penalizace
current_total_penalty -= get_penalty(root_i);
current_total_penalty -= get_penalty(root_j);
// 2. Sloučení dat do root_i
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
min_idx[root_i] = min(min_idx[root_i], min_idx[root_j]);
min_diff[0][root_i] = min(min_diff[0][root_i], min_diff[0][root_j]);
min_diff[1][root_i] = min(min_diff[1][root_i], min_diff[1][root_j]);
min_jump_diff[0][root_i] = min(min_jump_diff[0][root_i], min_jump_diff[0][root_j]);
min_jump_diff[1][root_i] = min(min_jump_diff[1][root_i], min_jump_diff[1][root_j]);
// 3. Přičteme novou penalizaci
current_total_penalty += get_penalty(root_i);
}
}
// Aktivace skoku (typ 2)
// Hrana (i, i+2) přeskakuje prvek m = i+1.
void activate_jump(int i, const vector<Artifact>& arts) {
int skipped_idx = i + 1;
int p = skipped_idx % 2; // Parita přeskočeného prvku
int root = find(i); // Hledáme kořen komponenty, kde skok je
// Zkontrolujeme, jestli se tímto skokem nezlepší "min_jump_diff" pro danou paritu
if (arts[skipped_idx].diff < min_jump_diff[p][root]) {
current_total_penalty -= get_penalty(root);
min_jump_diff[p][root] = arts[skipped_idx].diff;
current_total_penalty += get_penalty(root);
}
}
};
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int n = W.size();
vector<Artifact> arts(n);
ll base_cost = 0;
for(int i=0; i<n; ++i) {
arts[i] = {i, W[i], (ll)A[i] - B[i]};
base_cost += B[i];
}
// Seřadíme podle váhy W
sort(arts.begin(), arts.end(), [](const Artifact& a, const Artifact& b){
return a.w < b.w;
});
// Vytvoříme události
vector<Event> events;
events.reserve(2 * n + E.size());
// Hrany Type 1: (i, i+1)
for(int i=0; i < n-1; ++i) {
events.push_back({arts[i+1].w - arts[i].w, 1, i});
}
// Hrany Type 2: (i, i+2) - Skoky
for(int i=0; i < n-2; ++i) {
events.push_back({arts[i+2].w - arts[i].w, 2, i});
}
// Dotazy
for(int i=0; i < E.size(); ++i) {
events.push_back({E[i], 3, i});
}
sort(events.begin(), events.end());
// Inicializace DSU (musí pracovat s indexy po seřazení 0..N-1)
DSU dsu(n, arts);
vector<ll> results(E.size());
for(const auto& ev : events) {
if (ev.type == 1) {
dsu.unite(ev.idx, ev.idx+1);
} else if (ev.type == 2) {
// Index v eventu je 'i', skok je přes 'i+1' (v seřazeném poli)
dsu.activate_jump(ev.idx, arts);
} else {
// Query
results[ev.idx] = base_cost + dsu.current_total_penalty;
}
}
return results;
}
