Submission #1289698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289698		SamueleVid	Port Facility (JOI17_port_facility)	C++20	100 / 100	880 ms	367748 KiB

port_facility

#include <cstdio>      // Per scanf/printf
#include <vector>
#include <algorithm>   // Per sort
#include <numeric>     // Per fill

// Usiamo lo namespace std per brevità, come nell'originale
using namespace std;

// Definiamo un tipo per gli intervalli per chiarezza
using Interval = pair<int, int>;

// Costanti globali
const int LOG_MAX_COORD = 21;                 // Logaritmo della coordinata massima (2^21)
const int MAX_COORD = 1 << LOG_MAX_COORD;   // Coordinata massima possibile
const int MOD = 1000000007;

// --- Classe Union-Find (Disjoint Set Union) per 2-SAT ---
// Gestisce i set disgiunti per tracciare i vincoli 2-SAT.
// Ogni variabile 'v' è rappresentata da due nodi:
// - v * 2       (rappresenta 'v è vero')
// - v * 2 + 1   (rappresenta 'v è falso')
class UnionFind
{
public:
    // parent[i] = genitore del nodo i
    // rank[i] = rango (profondità) dell'albero radicato in i
    int parent[MAX_COORD * 2];
    int rank[MAX_COORD * 2];

    // Inizializza la struttura: ogni nodo è genitore di sé stesso
    void init()
    {
        for (int i = 0; i < MAX_COORD * 2; i++)
        {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // Trova il rappresentante (radice) del set contenente 'a'
    // Usa la "path compression" per efficienza
    int find_set(int a)
    {
        if (a == parent[a])
            return a;
        else
            return parent[a] = find_set(parent[a]);
    }

    // Unisce i due set che contengono 'a' e 'b'
    // Usa "union by rank" per efficienza
    void unite_sets(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
        if (a == b)
            return; // Già uniti

        if (rank[a] > rank[b])
        {
            parent[b] = a;
        }
        else
        {
            parent[a] = b;
        }
        if (rank[a] == rank[b])
            rank[b]++;
    }
};

// Istanza globale della struttura Union-Find
UnionFind uf;

// Aggiunge un vincolo 2-SAT tra due variabili (identificate dai loro tempi di inizio)
// 'start_time_1' e 'start_time_2' sono gli ID delle variabili.
void add_2sat_constraint(int start_time_1, int start_time_2, bool must_be_same)
{
    // ID dei nodi 'true' e 'false' per la variabile 1
    int v1_true = start_time_1 * 2;
    int v1_false = start_time_1 * 2 + 1;
    // ID dei nodi 'true' e 'false' per la variabile 2
    int v2_true = start_time_2 * 2;
    int v2_false = start_time_2 * 2 + 1;

    if (must_be_same)
    {
        // Vincolo: v1 <-> v2  (devono avere lo stesso valore)
        // Questo equivale a (v1 -> v2) AND (v2 -> v1)
        // Che in 2-SAT si traduce in:
        // (NOT v1 OR v2) -> unisci(v1_false, v2_true)
        // (NOT v2 OR v1) -> unisci(v2_false, v1_true)
        // Il codice originale unisce (v1_true, v2_true) e (v1_false, v2_false),
        // che è un'implementazione equivalente e più diretta per l'implicazione <->
        uf.unite_sets(v1_true, v2_true);
        uf.unite_sets(v1_false, v2_false);
    }
    else
    {
        // Vincolo: v1 <-> NOT v2 (devono avere valori diversi)
        // (v1 -> NOT v2) AND (NOT v2 -> v1)
        // (NOT v1 OR NOT v2) -> unisci(v1_false, v2_false)
        // (v2 OR v1)       -> unisci(v2_true, v1_true)
        // L'implementazione del codice originale è:
        uf.unite_sets(v1_true, v2_false);
        uf.unite_sets(v1_false, v2_true);
    }
}

// --- Classe Segment Tree ---
// Questo non è un Segment Tree standard. È una struttura usata per
// decomporre gli intervalli e trovare efficientemente le sovrapposizioni.
class IntervalSegmentTree
{
public:
    // Ogni nodo dell'albero contiene un vettore di intervalli
    vector<Interval> node_intervals[1 << (LOG_MAX_COORD + 1)];
    // Flag globale per tracciare se una soluzione è possibile
    bool is_possible;

    // Array temporanei usati in solve2/solve3 per evitare riallocazioni
    int temp_idx[MAX_COORD];
    int temp_imos[MAX_COORD]; // "IMOS" è una tecnica di programmazione dinamica/prefix sum

    void init()
    {
        is_possible = true;
        for (int i = 0; i < (1 << (LOG_MAX_COORD + 1)); i++)
            node_intervals[i].clear();
    }

    // Aggiunge un intervallo [start, end] all'albero.
    // L'intervallo viene inserito nel nodo più alto (più vicino alla radice)
    // che "copre" l'intervallo, ma i cui figli non lo coprono completamente.
    void add_interval_to_tree(int start, int end)
    {
        int node_idx = 1;
        int lb = 0, ub = MAX_COORD - 1; // [lb, ub] è il range del nodo corrente
        for (;;)
        {
            int mid = (lb + ub) / 2;
            if (end <= mid)
            {
                // L'intervallo è tutto a sinistra
                ub = mid;
                node_idx = node_idx * 2;
            }
            else if (mid + 1 <= start)
            {
                // L'intervallo è tutto a destra
                lb = mid + 1;
                node_idx = node_idx * 2 + 1;
            }
            else
            {
                // L'intervallo scavalca il punto centrale (mid)
                // Questo è il nodo corretto dove memorizzare l'intervallo
                node_intervals[node_idx].push_back(make_pair(start, end));
                break;
            }
        }
    }

    // --- Funzioni di Elaborazione dei Nodi ---
    // Queste funzioni vengono chiamate durante la costruzione (calc())
    // per aggiungere i vincoli 2-SAT in base alle sovrapposizioni.

    // 1. process_node_internal_overlaps:
    // Aggiunge vincoli per intervalli che si sovrappongono e che sono
    // TUTTI memorizzati *direttamente* in questo nodo (node_intervals[node_idx]).
    void process_node_internal_overlaps(int node_idx)
    {
        // Ordina gli intervalli per tempo di inizio
        sort(node_intervals[node_idx].begin(), node_intervals[node_idx].end());

        // 'dominant_intervals': intervalli "dominanti" (con fine decrescente)
        // 'contained_intervals': intervalli "contenuti" (non dominanti)
        vector<Interval> dominant_intervals, contained_intervals;
        int min_end_so_far = 2e9; // Un numero grande

        for (int i = 0; i < node_intervals[node_idx].size(); i++)
        {
            if (min_end_so_far > node_intervals[node_idx][i].second)
            {
                min_end_so_far = node_intervals[node_idx][i].second;
                dominant_intervals.push_back(node_intervals[node_idx][i]);
            }
            else
            {
                contained_intervals.push_back(node_intervals[node_idx][i]);
            }
        }

        // Controllo di coerenza: se tre intervalli si sovrappongono a catena
        // in un modo particolare (A contiene B, B contiene C), può essere impossibile.
        // Questo controlla se gli intervalli "contenuti" sono ordinati
        // in modo non decrescente per 'end'. Se lo sono, c'è un conflitto.
        for (int i = 1; i < contained_intervals.size(); i++)
        {
            if (contained_intervals[i - 1].second < contained_intervals[i].second)
                is_possible = false;
        }

        // Aggiunge vincoli tra intervalli dominanti e contenuti che si sovrappongono
        int pt = 0;
        for (int i = 0; i < dominant_intervals.size(); i++)
        {
            for (;;)
            {
                if (pt == contained_intervals.size()) break;
                // Se l'intervallo dominante 'i' si sovrappone al contenuto 'pt'
                if (dominant_intervals[i].second > contained_intervals[pt].second) break;
                if (dominant_intervals[i].first < contained_intervals[pt].first)
                {
                    // Sovrapposizione trovata! Devono essere in gruppi diversi.
                    add_2sat_constraint(dominant_intervals[i].first, contained_intervals[pt].first, false);
                }
                pt++;
            }
            if (pt != 0) pt--;
        }
    }

    // 2. process_left_child_overlaps:
    // Aggiunge vincoli tra gli intervalli del *figlio sinistro* (node_idx * 2)
    // e gli intervalli di *questo nodo* (node_idx).
    void process_left_child_overlaps(int node_idx, int lb, int ub)
    {
        // [lb, ub] è il range del figlio sinistro
        int node_range_len = ub - lb + 1;
        fill(temp_idx, temp_idx + node_range_len, -1);
        fill(temp_imos, temp_imos + node_intervals[node_idx].size() + 1, 0);

        // Mappa le coordinate 'start' agli indici del vettore node_intervals[node_idx]
        for (int i = 0; i < node_intervals[node_idx].size(); i++)
            temp_idx[node_intervals[node_idx][i].first - lb] = i;
        for (int i = 1; i < node_range_len; i++)
            if (temp_idx[i] == -1) temp_idx[i] = temp_idx[i - 1];
        
        // Per ogni intervallo nel figlio sinistro...
        for (int i = 0; i < node_intervals[node_idx * 2].size(); i++)
        {
            Interval child_interval = node_intervals[node_idx * 2][i];
            int start_idx = temp_idx[child_interval.first - lb];
            int end_idx = temp_idx[child_interval.second - lb];

            if (start_idx < end_idx)
            {
                // L'intervallo del figlio [start, end] si sovrappone a un
                // range di intervalli [start_idx, end_idx] in questo nodo.
                // Usa la tecnica IMOS (array delle differenze) per marcare il range.
                temp_imos[start_idx + 1]++;
                temp_imos[end_idx]--;

                // Aggiunge vincolo tra l'intervallo figlio e l'intervallo 'end_idx'
                // (l'ultimo intervallo del nodo padre con cui si sovrappone)
                add_2sat_constraint(child_interval.first, node_intervals[node_idx][end_idx].first, false);
            }
        }

        // Calcola la somma prefissa (prefix sum) dell'array IMOS
        for (int i = 1; i <= node_intervals[node_idx].size(); i++)
            temp_imos[i] += temp_imos[i - 1];

        // Se imos[i] > 0, significa che l'intervallo 'i' di questo nodo
        // è sovrapposto da *almeno un* intervallo del figlio sinistro.
        // Se imos[i] > 0, allora gli intervalli 'i' e 'i+1' di questo nodo
        // devono essere messi *nello stesso gruppo* (true).
        for (int i = 0; i < int(node_intervals[node_idx].size()) - 1; i++)
            if (temp_imos[i] > 0)
                add_2sat_constraint(node_intervals[node_idx][i].first, node_intervals[node_idx][i + 1].first, true);
    }


    // 3. process_right_child_overlaps:
    // Simmetrico a process_left_child_overlaps, ma per il *figlio destro*.
    // Usa un trucco di ordinamento (swap/sort/swap) per ordinare per 'end'
    // e riutilizzare la stessa logica.
    void process_right_child_overlaps(int node_idx, int lb, int ub)
    {
        // [lb, ub] è il range del figlio destro

        // Ordina per 'end'
        for (int i = 0; i < node_intervals[node_idx].size(); i++)
            swap(node_intervals[node_idx][i].first, node_intervals[node_idx][i].second);
        sort(node_intervals[node_idx].begin(), node_intervals[node_idx].end());
        for (int i = 0; i < node_intervals[node_idx].size(); i++)
            swap(node_intervals[node_idx][i].first, node_intervals[node_idx][i].second);

        // La logica è identica a 'process_left_child_overlaps',
        // ma ora 'temp_idx' mappa le coordinate 'end'
        int node_range_len = ub - lb + 1;
        fill(temp_idx, temp_idx + node_range_len, -1);
        fill(temp_imos, temp_imos + node_intervals[node_idx].size() + 1, 0);

        for (int i = 0; i < node_intervals[node_idx].size(); i++)
            temp_idx[node_intervals[node_idx][i].second - lb] = i;
        for (int i = 1; i < node_range_len; i++)
            if (temp_idx[i] == -1) temp_idx[i] = temp_idx[i - 1];

        for (int i = 0; i < node_intervals[node_idx * 2 + 1].size(); i++)
        {
            Interval child_interval = node_intervals[node_idx * 2 + 1][i];
            int start_idx = temp_idx[child_interval.first - lb];
            int end_idx = temp_idx[child_interval.second - lb];

            if (start_idx < end_idx)
            {
                temp_imos[start_idx + 1]++;
                temp_imos[end_idx]--;
                add_2sat_constraint(child_interval.first, node_intervals[node_idx][end_idx].first, false);
            }
        }

        for (int i = 1; i <= node_intervals[node_idx].size(); i++)
            temp_imos[i] += temp_imos[i - 1];

        for (int i = 0; i < int(node_intervals[node_idx].size()) - 1; i++)
            if (temp_imos[i] > 0)
                add_2sat_constraint(node_intervals[node_idx][i].first, node_intervals[node_idx][i + 1].first, true);
    }


    // Funzione principale che costruisce l'albero e tutti i vincoli
    // Procede "bottom-up", dalle foglie (livello LOG-1) alla radice (livello 0)
    void build_constraints()
    {
        for (int level = LOG_MAX_COORD - 1; level >= 0; level--)
        {
            for (int j = 0; j < (1 << level); j++)
            {
                int node_idx = (1 << level) + j;
                int node_lb = j << (LOG_MAX_COORD - level);
                int node_ub = ((j + 1) << (LOG_MAX_COORD - level)) - 1;
                int node_mid = node_lb + (1 << (LOG_MAX_COORD - 1 - level)) - 1;

                // 1. Processa sovrapposizioni interne al nodo
                process_node_internal_overlaps(node_idx);
                
                // 2. Processa sovrapposizioni tra figlio sx e nodo
                process_left_child_overlaps(node_idx, node_lb, node_mid);
                
                // 3. Processa sovrapposizioni tra figlio dx e nodo
                process_right_child_overlaps(node_idx, node_mid + 1, node_ub);

                // "Sposta" (copia) gli intervalli dai figli a questo nodo
                // per l'elaborazione al livello superiore
                for (int k = 0; k < node_intervals[node_idx * 2].size(); k++)
                    node_intervals[node_idx].push_back(node_intervals[node_idx * 2][k]);
                for (int k = 0; k < node_intervals[node_idx * 2 + 1].size(); k++)
                    node_intervals[node_idx].push_back(node_intervals[node_idx * 2 + 1][k]);
            }
        }
    }
};

// --- Funzione Main ---
int main()
{
    int num_intervals;
    scanf("%d", &num_intervals);

    IntervalSegmentTree tree;
    tree.init();
    uf.init();

    vector<Interval> input_intervals;
    for (int i = 0; i < num_intervals; i++)
    {
        int start, end;
        scanf("%d%d", &start, &end);
        start--, end--; // 0-indexa le coordinate
        input_intervals.push_back(make_pair(start, end));
        tree.add_interval_to_tree(start, end);
    }

    // Costruisce la struttura e aggiunge tutti i vincoli 2-SAT
    tree.build_constraints();

    // --- Controllo Finale e Calcolo della Risposta ---

    // 1. Controlla se c'è una contraddizione (v <-> NOT v)
    // Se per qualsiasi variabile 'v', 'v' e 'NOT v' sono nello stesso set,
    // allora è impossibile.
    for (int i = 0; i < num_intervals; i++)
    {
        int start_time = input_intervals[i].first;
        if (uf.find_set(start_time * 2) == uf.find_set(start_time * 2 + 1))
        {
            tree.is_possible = false;
        }
    }

    // 2. Conta le componenti connesse
    // Se la soluzione è valida, il numero di modi per assegnare le gru
    // è 2 elevato al numero di "scelte indipendenti".
    // Contiamo il numero di radici (rappresentanti) nel DSU
    // tra tutte le variabili (v_true e v_false).
    int num_components = 0;
    for (int i = 0; i < num_intervals; i++)
    {
        int start_time = input_intervals[i].first;
        // Controlla il nodo 'true'
        if (uf.find_set(start_time * 2) == start_time * 2)
            num_components++;
        // Controlla il nodo 'false'
        if (uf.find_set(start_time * 2 + 1) == start_time * 2 + 1)
            num_components++;
    }

    // Se non è possibile, 'ans' è 0
    // Altrimenti, 'ans' è 1
    long long ans = tree.is_possible ? 1 : 0;

    // Il numero di scelte indipendenti è num_components / 2
    // Calcoliamo (ans * 2^(num_components / 2)) % MOD
    for (int i = 0; i < num_components / 2; i++)
    {
        ans = (ans * 2) % MOD;
    }

    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:361:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  361 |     scanf("%d", &num_intervals);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:371:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  371 |         scanf("%d%d", &start, &end);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22