Submission #1303892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303892		chaitanyamehta	Curtains (NOI23_curtains)	C++20	0 / 100	0 ms	568 KiB

curtains

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

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

    int n, m;
    cin >> n >> m;
    vector<int> mx(n+2, 0);      // mx[i] = max r among intervals with left == i
    for(int i=1;i<=n;i++) mx[i] = i-1; // default: cannot cover starting at i

    for(int i=0;i<m;i++){
        int l, r; cin >> l >> r;
        if(l < 1) l = 1;
        if(l > n) continue;
        mx[l] = max(mx[l], r);
    }

    // Build sparse table on mx for range-maximum queries
    int LOG = 1;
    while((1<<LOG) <= n) ++LOG;
    vector<vector<int>> st(LOG, vector<int>(n+2));
    for(int i=1;i<=n;i++) st[0][i] = mx[i];
    for(int k=1;k<LOG;k++){
        int len = 1<<(k-1);
        for(int i=1;i + (1<<k) - 1 <= n; i++){
            st[k][i] = max(st[k-1][i], st[k-1][i+len]);
        }
    }
    auto rmq = [&](int l, int r)->int{
        if(l > r) return l-1; // no valid interval -> return a "stuck" value
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len);
        return max(st[k][l], st[k][r - (1<<k) + 1]);
    };

    // Build binary-lifting table up[k][i] = farthest reach from i using <= 2^k intervals
    vector<vector<int>> up(LOG, vector<int>(n+2));
    for(int i=1;i<=n;i++) up[0][i] = mx[i];
    for(int k=1;k<LOG;k++){
        for(int i=1;i<=n;i++){
            int mid = up[k-1][i];
            up[k][i] = rmq(i, mid); // max mx[j] for j in [i..mid]
        }
    }

    int q; cin >> q;
    while(q--){
        int s,e; cin >> s >> e;
        if(s < 1) s = 1;
        if(e > n) e = n;
        if(s > e){
            cout << "No\n";
            continue;
        }

        // If no interval starting at s can cover s, impossible
        if(mx[s] < s){
            cout << "No\n";
            continue;
        }

        int pos = s;
        if(pos > e){
            cout << "Yes\n";
            continue;
        }

        // If already mx[s] >= e then covered by one or more intervals that start at s (maybe one)
        // We'll use binary lifting to jump as far as needed
        for(int k = LOG-1; k >= 0; --k){
            int reach = up[k][pos];
            if(reach < e){
                // If reach did not advance, stuck -> impossible
                if(reach < pos){
                    pos = n+1; // force fail
                    break;
                }
                pos = reach + 1;
                if(pos > e) break;
            }
        }

        bool ok = false;
        if(pos <= e){
            // Need one final interval starting at pos to cover remaining part
            if(mx[pos] >= e) ok = true;
            else ok = false;
        } else {
            // pos > e => covered already
            ok = true;
        }

        cout << (ok ? "Yes\n" : "No\n");
    }

    return 0;
}

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