#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; }