제출 #1317364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317364		spetr	나일강 (IOI24_nile)	C++20	51 / 100	67 ms	12948 KiB

nile

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()

// Struktura pro reprezentaci artefaktu po seřazení
struct Artifact {
    int id;
    int w, a, b;
    ll diff; // cena navíc za to, že je sám (A - B)
};

// Struktura pro DSU (Disjoint Set Union)
struct DSU {
    vector<int> parent;
    vector<int> sz; // velikost komponenty
    // min_p[0] ukládá min(A-B) pro prvky s globálním sudým indexem v této komponentě
    // min_p[1] ukládá min(A-B) pro prvky s globálním lichým indexem
    vector<ll> min_p[2]; 
    vector<bool> can_swap; // Existuje uvnitř komponenty hrana délky 2?
    
    // Globální součet penalizací (pro liché komponenty)
    ll total_penalty = 0;

    DSU(int n, const vector<Artifact>& arts) {
        parent.resize(n);
        iota(all(parent), 0);
        sz.assign(n, 1);
        min_p[0].assign(n, 2e18); // Inicializace nekonečnem
        min_p[1].assign(n, 2e18);
        can_swap.assign(n, false);

        for(int i=0; i<n; ++i) {
            min_p[i%2][i] = arts[i].diff; // Nastavíme počáteční diff
            total_penalty += arts[i].diff; // Na začátku jsou všichni sami (ostrůvky velikosti 1)
        }
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    // Pomocná funkce pro výpočet penalizace konkrétní komponenty (reprezentované kořenem root)
    ll get_component_penalty(int root) {
        if (sz[root] % 2 == 0) return 0; // Sudá délka -> všichni spárovaní, žádné penále
        
        // Lichá délka: Musíme nechat jednoho samotného.
        // Standardně musí mít stejnou paritu jako "většina" v komponentě.
        // Ale DSU neví, kde komponenta začíná, tak to určíme trikem:
        // V liché komponentě je počet sudých a lichých indexů různý. 
        // Ten typ indexu, kterého je víc, je "většinový".
        // Protože min_p[0] a min_p[1] drží globální parity, stačí porovnat, 
        // která parita má víc "zástupců"? Ne, to je složité sledovat.
        
        // Jednodušší: V liché komponentě o 1 prvku (index i) je "většina" parita (i%2).
        // Při spojování (SUDÁ + LICHÁ -> LICHÁ) se parita většiny nemění.
        // Při spojování (LICHÁ + LICHÁ -> SUDÁ) penále zmizí.
        // Takže nám stačí vědět, jakou paritu má "většina".
        // Ale my ani to nepotřebujeme. 
        // V liché komponentě existuje jedna parita, která má o 1 prvek víc.
        // Řekněme, že parita P je majoritní. Musíme obětovat někoho z P.
        // Pokud máme swap, můžeme obětovat někoho z !P.
        
        // Jak poznat majoritní paritu?
        // Při inicializaci (velikost 1, index i) je majorita (i%2).
        // Uložíme si typ majority do DSU?
        // Ne, stačí sledovat min_p.
        // Pro liché komponenty vždy platí: Jeden typ parity je "nucený" (ten co má víc prvků).
        // V našem kódu níže budeme merge provádět opatrně a paritu si odvodíme.
        // Vlastně: Artifacty jsou seřazené. Komponenta je vždy INTERVAL [L, R].
        // Pokud je délka liché, majoritní parita je L%2.
        
        // Ale DSU nedrží L a R. Ale my víme, že hrany jsou jen (i, i+1). 
        // Takže v každé komponentě je `min_index` ten L.
        // Můžeme si držet `min_index` v DSU.
        return 0; // Placeholder, logika je přímo v unite/activate
    }
    
    // Protože get_component_penalty je složitější implementovat čistě,
    // budeme udržovat `total_penalty` inkrementálně při operacích.
    // Abychom to zvládli, potřebujeme uvnitř DSU vědět, která parita je ta "hlavní".
    // Přidáme si do DSU `start_index`.
    vector<int> start_index; 
    // Pro konstruktor: start_index[i] = i;
    
    // Skutečná funkce pro výpočet penále:
    ll calc_penalty(int root) {
        if (sz[root] % 2 == 0) return 0;
        
        int majority_parity = start_index[root] % 2;
        ll cost = min_p[majority_parity][root]; // Cena když obětujeme někoho z majority
        
        if (can_swap[root]) {
            cost = min(cost, min_p[1 - majority_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) {
            // Odečteme staré penále
            total_penalty -= calc_penalty(root_i);
            total_penalty -= calc_penalty(root_j);

            // Merge (union by size/random, here simply attach j to i)
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            
            // Update minim
            min_p[0][root_i] = min(min_p[0][root_i], min_p[0][root_j]);
            min_p[1][root_i] = min(min_p[1][root_i], min_p[1][root_j]);
            
            // Update swap a start index (start index je min z obou)
            can_swap[root_i] = can_swap[root_i] | can_swap[root_j];
            start_index[root_i] = min(start_index[root_i], start_index[root_j]);

            // Přičteme nové penále
            total_penalty += calc_penalty(root_i);
        }
    }

    void activate_swap(int i) {
        int root = find(i);
        if (!can_swap[root]) {
            total_penalty -= calc_penalty(root);
            can_swap[root] = true;
            total_penalty += calc_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; // Součet všech B (kdyby bylo vše spárováno)

    for(int i=0; i<n; ++i) {
        arts[i] = {i, W[i], A[i], B[i], (ll)A[i] - B[i]};
        base_cost += B[i];
    }
    sort(all(arts), [](const Artifact& a, const Artifact& b){
        return a.w < b.w;
    });

    // Eventy: {weight, type, index}
    // Type 1: Edge (i, i+1) -> weight = W[i+1] - W[i]
    // Type 2: Edge (i, i+2) -> weight = W[i+2] - W[i]
    // Type 3: Query -> weight = E[i]
    struct Event {
        int w, type, idx;
        bool operator<(const Event& other) const {
            if (w != other.w) return w < other.w;
            return type < other.type; // Nejdřív hrany (1,2), pak dotazy (3)
        }
    };

    vector<Event> events;
    for(int i=0; i < n-1; ++i) {
        events.push_back({arts[i+1].w - arts[i].w, 1, i});
    }
    for(int i=0; i < n-2; ++i) {
        events.push_back({arts[i+2].w - arts[i].w, 2, i});
    }
    for(int i=0; i < E.size(); ++i) {
        events.push_back({E[i], 3, i});
    }
    sort(all(events));

    // Inicializace DSU
    // Pozor: DSU potřebuje pracovat s indexy v poli `arts` (0..n-1), ne původními ID
    // Ale protože jsme sortovali `arts`, indexy 0..n-1 v DSU odpovídají seřazenému poli.
    // Musíme ale správně nastavit start_index
    DSU dsu(n, arts);
    dsu.start_index.resize(n);
    iota(all(dsu.start_index), 0);

    vector<ll> results(E.size());

    for(auto& ev : events) {
        if (ev.type == 1) {
            // Spojení i a i+1
            dsu.unite(ev.idx, ev.idx+1);
        } else if (ev.type == 2) {
            // Aktivace swapu pro komponentu obsahující i (a tím pádem i i+2)
            // Poznámka: Pokud hrana (i, i+2) je aktivní, pak (i, i+1) a (i+1, i+2)
            // jsou zaručeně taky aktivní (díky trojúhelníkové nerovnosti na 1D přímce).
            // Takže i a i+2 jsou už ve stejné komponentě.
            dsu.activate_swap(ev.idx);
        } else {
            // Query
            results[ev.idx] = base_cost + dsu.total_penalty;
        }
    }

    return results;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18