#include <vector> #include <algorithm> #include <numeric> #include <iostream> using namespace std; typedef long long ll; struct Artifact { int id; int w; ll diff; // Cena navíc za to, že je sám (A - B) }; struct Event { int w; // Váha hrany nebo dotazu int type; // 1: Hrana (i, i+1), 2: Hrana (i, i+2), 3: Dotaz int idx; // Index // Řazení: Podle váhy. Při shodě vah mají přednost hrany před dotazy (Type 1/2 < Type 3) 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<ll> min_diff[2]; // min_diff[0]: min(A-B) pro sudé indexy, [1] pro liché vector<int> min_idx; // Nejnižší index v komponentě (určuje paritu majority) vector<bool> can_swap; // Máme hranu typu 2 (skok)? ll current_penalty = 0; // Součet penalizací všech LICHÝCH komponent DSU(int n, const vector<Artifact>& arts) { parent.resize(n); iota(parent.begin(), parent.end(), 0); sz.assign(n, 1); min_diff[0].assign(n, 2e18); // Inicializace "nekonečnem" min_diff[1].assign(n, 2e18); min_idx.resize(n); can_swap.assign(n, false); for(int i=0; i<n; ++i) { min_diff[i%2][i] = arts[i].diff; min_idx[i] = i; // Na začátku je každý sám -> lichá komponenta -> platí diff current_penalty += arts[i].diff; } } int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } // Vypočítá penalizaci pro jednu konkrétní komponentu ll get_penalty(int root) { if (sz[root] % 2 == 0) return 0; // Sudá velikost = 0 penále // Lichá velikost: // Komponenta je vždy souvislý interval [L, R] (díky vlastnosti Type 1 hran). // Majoritní parita (ta, které je o 1 víc) je parita L (min_idx). int major_parity = min_idx[root] % 2; ll val = min_diff[major_parity][root]; // Musíme obětovat někoho z majority if (can_swap[root]) { // Pokud máme skok, můžeme obětovat někoho z minority, pokud je to levnější val = min(val, min_diff[1 - major_parity][root]); } return val; } 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) if (sz[root_i] < sz[root_j]) swap(root_i, root_j); // Odečteme staré penalizace current_penalty -= get_penalty(root_i); current_penalty -= get_penalty(root_j); // Sloučení (j do i) parent[root_j] = root_i; sz[root_i] += sz[root_j]; // Aktualizace vlastností kořene 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_idx[root_i] = min(min_idx[root_i], min_idx[root_j]); can_swap[root_i] = can_swap[root_i] | can_swap[root_j]; // Přičteme novou penalizaci spojené komponenty current_penalty += get_penalty(root_i); } } void activate_swap(int i) { int root = find(i); if (!can_swap[root]) { current_penalty -= get_penalty(root); can_swap[root] = true; current_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_B_sum = 0; // Základní cena, kdybychom všechno spárovali (suma B) for(int i=0; i<n; ++i) { arts[i] = {i, W[i], (ll)A[i] - B[i]}; base_B_sum += B[i]; } // Seřadíme artefakty podle váhy sort(arts.begin(), arts.end(), [](const Artifact& a, const Artifact& b){ return a.w < b.w; }); vector<Event> events; events.reserve(2 * n + E.size()); // Prealokace pro rychlost // 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()); 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) { dsu.activate_swap(ev.idx); } else { // Výsledek = Suma B + penalizace za liché prvky results[ev.idx] = base_B_sum + dsu.current_penalty; } } return results; }