Submission #1303906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303906		chaitanyamehta	Curtains (NOI23_curtains)	C++20	20 / 100	375 ms	58380 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

struct DSUNext {
    int n;
    vector<int> parent;
    DSUNext(int n=0){ init(n); }
    void init(int n_) {
        n = n_;
        parent.resize(n+2);
        for(int i=0;i<=n+1;i++) parent[i]=i;
    }
    int find(int x){
        // find next index >= x that is not yet "removed" (not covered)
        if(x > n+1) return x;
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    void remove(int x){
        // mark x as removed/covered: next available becomes x+1
        parent[x] = x+1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    if(!(cin >> n >> m >> q)) return 0;

    vector<vector<pair<int,int>>> bucket(n+1); // bucket[r] holds intervals (l,r)
    for(int i=0;i<m;i++){
        int l, r; cin >> l >> r;
        if(l < 1) l = 1;
        if(r > n) r = n;
        if(l > r) continue;
        bucket[r].push_back({l, r});
    }

    // read queries and group them by their e (right endpoint)
    vector<vector<pair<int,int>>> queries_by_e(n+1);
    vector<string> ans; ans.reserve(q);
    // store index for answer ordering
    vector<int> q_s(q), q_e(q);
    for(int i=0;i<q;i++){
        int s, e; cin >> s >> e;
        if(s < 1) s = 1;
        if(e > n) e = n;
        q_s[i] = s; q_e[i] = e;
        if(e < 0) e = 0;
        if(e > n) e = n;
        queries_by_e[e].push_back({s, i});
    }

    DSUNext dsu(n);
    vector<char> covered(n+2, 0);
    vector<char> answer(q, 0);

    // sweep R from 1..n
    for(int R = 1; R <= n; ++R){
        // add all intervals with right == R
        for(auto &pr : bucket[R]){
            int L = pr.first;
            int r = pr.second; // equals R
            int pos = dsu.find(L);
            while(pos <= r){
                covered[pos] = 1;
                dsu.remove(pos);           // mark pos as covered -> parent[pos] = pos+1
                pos = dsu.find(pos);       // jump to next uncovered
            }
        }

        // answer queries with e == R
        for(auto &qi : queries_by_e[R]){
            int s = qi.first;
            int idx = qi.second;
            int pos = dsu.find(s);
            if(pos > R) answer[idx] = 1; // fully covered
            else answer[idx] = 0;
        }
    }

    // Edge-case: queries with e == 0 (if any) — none covered
    if(0 <= n){
        for(auto &qi : queries_by_e[0]){
            int idx = qi.second;
            answer[idx] = 0;
        }
    }

    // print answers in original order
    for(int i=0;i<q;i++){
        cout << (answer[i] ? "YES" : "NO") << '\n';
    }

    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