제출 #1261495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261495		liangjeremy	Curtains (NOI23_curtains)	C++20	20 / 100	193 ms	11856 KiB

curtains

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// Fast I/O
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

//--- Solution for Subtask 3 (and all smaller subtasks) ---//
// Algorithm: Dynamic Programming / Greedy Precomputation
// Complexity: O(n^2 + m + q)
// This approach is suitable for n <= 2000.
void solve_subtask_3() {
    int n, m, q;
    std::cin >> n >> m >> q;

    // 1. Pre-calculate max endpoint 'r' for each start point 'l'
    std::vector<int> max_r_at(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int l, r;
        std::cin >> l >> r;
        max_r_at[l] = std::max(max_r_at[l], r);
    }

    // 2. Precompute all possible [s, e] ranges
    // possible[s][e] will be true if the range [s, e] can be exactly covered.
    std::vector<std::vector<bool>> possible(n + 1, std::vector<bool>(n + 1, false));

    for (int s = 1; s <= n; ++s) {
        int max_reach = s - 1; // Tracks the farthest point covered in a block starting at 's'
        for (int i = s; i <= n; ++i) {
            // If the current position 'i' is adjacent to our covered block
            if (i <= max_reach + 1) {
                // We can potentially extend our reach using a curtain starting at 'i'
                max_reach = std::max(max_reach, max_r_at[i]);
            }
            
            // If our contiguous block now covers all sections up to 'i'
            if (max_reach >= i) {
                possible[s][i] = true;
            }
        }
    }

    // 3. Answer queries in O(1) each
    for (int j = 0; j < q; ++j) {
        int s, e;
        std::cin >> s >> e;
        if (possible[s][e]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}


//--- Solution for Subtask 4 (s[j] = 1) ---//
// Algorithm: Offline processing with Disjoint Set Union (DSU)
// Complexity: O((m + q) * alpha(n))
// This is a highly efficient approach for the specific case where all queries start at 1.

// DSU data structure
struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        // Initially, the furthest reach from i is just i itself
        std::iota(parent.begin(), parent.end(), 0); 
    }

    // Find the representative (furthest reach) with path compression
    int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    // Union two sets
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // The new reach is the maximum of the two
            if (root_i > root_j) {
                parent[root_j] = root_i;
            } else {
                parent[root_i] = root_j;
            }
        }
    }
};

struct Curtain {
    int l, r;
};

struct Query {
    int e, id;
};

void solve_subtask_4() {
    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<Curtain> curtains(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> curtains[i].l >> curtains[i].r;
    }

    std::vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        int s; // s is always 1, but we must read it
        std::cin >> s >> queries[i].e;
        queries[i].id = i;
    }

    // 1. Sort curtains and queries by their right endpoint
    std::sort(curtains.begin(), curtains.end(), [](const Curtain& a, const Curtain& b) {
        return a.r < b.r;
    });
    std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.e < b.e;
    });

    std::vector<bool> ans(q);
    DSU dsu(n);
    int curtain_idx = 0;

    // 2. Process queries in sorted order
    for (const auto& query : queries) {
        // Add all curtains that are now available (r <= current query's e)
        while (curtain_idx < m && curtains[curtain_idx].r <= query.e) {
            int l = curtains[curtain_idx].l;
            int r = curtains[curtain_idx].r;
            
            // This curtain creates a bridge from l-1 to r.
            // We merge all reachable segments from l-1 onwards that are less than r.
            // This loop is efficient because `pos` always jumps over an entire merged set.
            for (int pos = dsu.find(l - 1); pos < r; pos = dsu.find(pos + 1)) {
                 dsu.unite(pos, r);
            }
            curtain_idx++;
        }

        // 3. Check if we can cover [1, e]
        // The DSU root of 0 (representing before section 1) tells us the max reach from the start.
        ans[query.id] = (dsu.find(0) == query.e);
    }
    
    // 4. Print answers in original order
    for (int i = 0; i < q; ++i) {
        if (ans[i]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

int main() {
    setup_io();

    // To run the code for a specific subtask, call the corresponding function.
    // For the general case (Subtask 3 and below):
    // solve_subtask_3();
    
    // For the special case s[j]=1 (Subtask 4):
    solve_subtask_4();

    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20