Submission #1289687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289687		SamueleVid	Port Facility (JOI17_port_facility)	C++20	0 / 100	96 ms	131656 KiB

port_facility

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
#define SEGTREE_SIZE (1 << 21)
#define LOG 21

class UnionFind {
public:
    int parent[SEGTREE_SIZE * 2];
    int rank[SEGTREE_SIZE * 2];
    
    void init() {
        for (int i = 0; i < SEGTREE_SIZE * 2; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        
        if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            if (rank[x] == rank[y]) rank[y]++;
        }
    }
};

UnionFind uf;

// Aggiunge un vincolo tra due intervalli
void add_constraint(int interval_a, int interval_b, bool same_stack) {
    // Ogni intervallo ha due possibili posizioni: 
    // interval*2 = stack1, interval*2+1 = stack2
    
    if (same_stack) {
        // Stesso stack: (a0 <-> b0) e (a1 <-> b1)
        uf.unite(interval_a * 2, interval_b * 2);
        uf.unite(interval_a * 2 + 1, interval_b * 2 + 1);
    } else {
        // Stack diversi: (a0 <-> b1) e (a1 <-> b0)
        uf.unite(interval_a * 2, interval_b * 2 + 1);
        uf.unite(interval_a * 2 + 1, interval_b * 2);
    }
}

class IntervalSolver {
public:
    vector<pii> node_segments[1 << (LOG + 1)];  // Segmenti in ogni nodo
    bool is_valid;  // Se la soluzione è possibile
    
    void init() {
        is_valid = true;
        for (int i = 0; i < (1 << (LOG + 1)); i++) {
            node_segments[i].clear();
        }
    }
    
    // Aggiunge un intervallo al segment tree
    void add_interval(int start, int end) {
        int node = 1;
        int left = 0, right = (1 << LOG) - 1;
        
        while (true) {
            int mid = (left + right) / 2;
            
            if (end <= mid) {
                // Intervallo completamente a sinistra
                right = mid;
                node = node * 2;
            } else if (start >= mid + 1) {
                // Intervallo completamente a destra
                left = mid + 1;
                node = node * 2 + 1;
            } else {
                // Intervallo centrale (attraversa mid)
                node_segments[node].push_back(make_pair(start, end));
                break;
            }
        }
    }
    
    // Risolve i conflitti tra intervalli dello stesso nodo
    void solve_node_conflicts(int node, int left_bound, int right_bound) {
        if (node_segments[node].empty()) return;
        
        // Ordina gli intervalli per start point
        sort(node_segments[node].begin(), node_segments[node].end());
        
        vector<pii> non_nested, nested;
        int min_end = 1000000000;
        
        // Separa in non annidati e annidati
        for (int i = 0; i < node_segments[node].size(); i++) {
            if (node_segments[node][i].second < min_end) {
                min_end = node_segments[node][i].second;
                non_nested.push_back(node_segments[node][i]);
            } else {
                nested.push_back(node_segments[node][i]);
            }
        }
        
        // Verifica che gli intervalli annidati siano in ordine decrescente di end
        for (int i = 1; i < nested.size(); i++) {
            if (nested[i - 1].second < nested[i].second) {
                is_valid = false;
                return;
            }
        }
        
        // Aggiungi vincoli tra non_nested e nested
        int ptr = 0;
        for (int i = 0; i < non_nested.size(); i++) {
            while (ptr < nested.size() && nested[ptr].second < non_nested[i].second) {
                // Conflitto: devono avere stack diversi
                add_constraint(non_nested[i].first, nested[ptr].first, false);
                ptr++;
            }
            if (ptr > 0) ptr--;
        }
    }
    
    int temp_index[SEGTREE_SIZE];
    int prefix_sum[SEGTREE_SIZE];
    
    // Risolve conflitti tra nodo corrente e figlio sinistro
    void solve_left_child_conflicts(int node, int left_bound, int right_bound) {
        if (node_segments[node].empty() || node_segments[node * 2].empty()) return;
        
        int mid = (left_bound + right_bound) / 2;
        int left_size = mid - left_bound + 1;
        
        // Inizializza array temporanei
        fill(temp_index, temp_index + left_size, -1);
        fill(prefix_sum, prefix_sum + node_segments[node].size() + 1, 0);
        
        // Costruisci indice per mapping veloce
        for (int i = 0; i < node_segments[node].size(); i++) {
            int pos = node_segments[node][i].first - left_bound;
            if (pos < left_size) {
                temp_index[pos] = i;
            }
        }
        for (int i = 1; i < left_size; i++) {
            if (temp_index[i] == -1) {
                temp_index[i] = temp_index[i - 1];
            }
        }
        
        // Processa intervalli del figlio sinistro
        for (int i = 0; i < node_segments[node * 2].size(); i++) {
            int start_idx = node_segments[node * 2][i].first - left_bound;
            int end_idx = node_segments[node * 2][i].second - left_bound;
            
            if (start_idx < left_size && end_idx < left_size && 
                temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
                temp_index[start_idx] < temp_index[end_idx]) {
                prefix_sum[temp_index[start_idx] + 1]++;
                prefix_sum[temp_index[end_idx]]--;
            }
        }
        
        // Aggiungi vincoli per conflitti diretti
        for (int i = 0; i < node_segments[node * 2].size(); i++) {
            int start_idx = node_segments[node * 2][i].first - left_bound;
            int end_idx = node_segments[node * 2][i].second - left_bound;
            
            if (start_idx < left_size && end_idx < left_size && 
                temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
                temp_index[start_idx] < temp_index[end_idx]) {
                add_constraint(node_segments[node * 2][i].first, 
                             node_segments[node][temp_index[end_idx]].first, false);
            }
        }
        
        // Calcola prefix sum e aggiungi vincoli tra intervalli consecutivi
        for (int i = 1; i <= node_segments[node].size(); i++) {
            prefix_sum[i] += prefix_sum[i - 1];
        }
        for (int i = 0; i < (int)node_segments[node].size() - 1; i++) {
            if (prefix_sum[i] > 0) {
                add_constraint(node_segments[node][i].first, 
                             node_segments[node][i + 1].first, true);
            }
        }
    }
    
    // Risolve conflitti tra nodo corrente e figlio destro (simmetrico)
    void solve_right_child_conflicts(int node, int left_bound, int right_bound) {
        if (node_segments[node].empty() || node_segments[node * 2 + 1].empty()) return;
        
        int mid = (left_bound + right_bound) / 2;
        int right_start = mid + 1;
        int right_size = right_bound - right_start + 1;
        
        // Ordina gli intervalli per end point
        vector<pii> sorted_by_end = node_segments[node];
        for (int i = 0; i < sorted_by_end.size(); i++) {
            swap(sorted_by_end[i].first, sorted_by_end[i].second);
        }
        sort(sorted_by_end.begin(), sorted_by_end.end());
        for (int i = 0; i < sorted_by_end.size(); i++) {
            swap(sorted_by_end[i].first, sorted_by_end[i].second);
        }
        
        // Inizializza array temporanei
        fill(temp_index, temp_index + right_size, -1);
        fill(prefix_sum, prefix_sum + node_segments[node].size() + 1, 0);
        
        // Costruisci indice per end point
        for (int i = 0; i < sorted_by_end.size(); i++) {
            int pos = sorted_by_end[i].second - right_start;
            if (pos < right_size) {
                temp_index[pos] = i;
            }
        }
        for (int i = 1; i < right_size; i++) {
            if (temp_index[i] == -1) {
                temp_index[i] = temp_index[i - 1];
            }
        }
        
        // Processa intervalli del figlio destro
        for (int i = 0; i < node_segments[node * 2 + 1].size(); i++) {
            int start_idx = node_segments[node * 2 + 1][i].first - right_start;
            int end_idx = node_segments[node * 2 + 1][i].second - right_start;
            
            if (start_idx < right_size && end_idx < right_size && 
                temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
                temp_index[start_idx] < temp_index[end_idx]) {
                prefix_sum[temp_index[start_idx] + 1]++;
                prefix_sum[temp_index[end_idx]]--;
            }
        }
        
        // Aggiungi vincoli per conflitti diretti
        for (int i = 0; i < node_segments[node * 2 + 1].size(); i++) {
            int start_idx = node_segments[node * 2 + 1][i].first - right_start;
            int end_idx = node_segments[node * 2 + 1][i].second - right_start;
            
            if (start_idx < right_size && end_idx < right_size && 
                temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
                temp_index[start_idx] < temp_index[end_idx]) {
                add_constraint(node_segments[node * 2 + 1][i].first, 
                             sorted_by_end[temp_index[end_idx]].first, false);
            }
        }
        
        // Calcola prefix sum e aggiungi vincoli tra intervalli consecutivi
        for (int i = 1; i <= sorted_by_end.size(); i++) {
            prefix_sum[i] += prefix_sum[i - 1];
        }
        for (int i = 0; i < (int)sorted_by_end.size() - 1; i++) {
            if (prefix_sum[i] > 0) {
                add_constraint(sorted_by_end[i].first, sorted_by_end[i + 1].first, true);
            }
        }
    }
    
    // Calcola la soluzione con divide and conquer
    void solve() {
        for (int level = LOG - 1; level >= 0; level--) {
            for (int node_idx = 0; node_idx < (1 << level); node_idx++) {
                int node = (1 << level) + node_idx;
                int segment_start = node_idx << (LOG - level);
                int segment_end = ((node_idx + 1) << (LOG - level)) - 1;
                
                if (!is_valid) return;
                
                solve_node_conflicts(node, segment_start, segment_end);
                solve_left_child_conflicts(node, segment_start, segment_end);
                solve_right_child_conflicts(node, segment_start, segment_end);
                
                // Merge degli intervalli dai figli
                for (int i = 0; i < node_segments[node * 2].size(); i++) {
                    node_segments[node].push_back(node_segments[node * 2][i]);
                }
                for (int i = 0; i < node_segments[node * 2 + 1].size(); i++) {
                    node_segments[node].push_back(node_segments[node * 2 + 1][i]);
                }
            }
        }
    }
};

IntervalSolver solver;

int main() {
    int num_intervals;
    scanf("%d", &num_intervals);
    
    solver.init();
    vector<pii> intervals;
    
    // Lettura input
    for (int i = 0; i < num_intervals; i++) {
        int start, end;
        scanf("%d%d", &start, &end);
        start--; end--;
        intervals.push_back(make_pair(start, end));
        solver.add_interval(start, end);
    }
    
    uf.init();
    solver.solve();
    
    // Verifica consistenza
    for (int i = 0; i < num_intervals; i++) {
        if (uf.find(intervals[i].first * 2) == uf.find(intervals[i].first * 2 + 1)) {
            solver.is_valid = false;
            break;
        }
    }
    
    if (!solver.is_valid) {
        printf("0\n");
        return 0;
    }
    
    // Conta componenti connesse
    int component_count = 0;
    for (int i = 0; i < num_intervals; i++) {
        if (uf.find(intervals[i].first * 2) == intervals[i].first * 2) {
            component_count++;
        }
        if (uf.find(intervals[i].first * 2 + 1) == intervals[i].first * 2 + 1) {
            component_count++;
        }
    }
    
    int result = 1;
    int mod = 1000000007;
    for (int i = 0; i < component_count / 2; i++) {
        result = (result * 2) % mod;
    }
    
    printf("%d\n", result);
    return 0;
}

Compilation message (stderr)

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

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