Submission #1249775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249775		mr_fin	Curtains (NOI23_curtains)	C++20	0 / 100	0 ms	324 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

int lg2(int n){
    return 31 - __builtin_clz(n);
}

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

    int n, m, q;
    cin >> n >> m >> q;

    // --- 1) Tính farL và farR ---
    // farL[i] = max r của curtain bắt đầu tại i
    // farR[i] = min l của curtain kết thúc tại i
    vi farL(n+2, 0), farR(n+2, n+1);
    for(int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        farL[l] = max(farL[l], r);
        farR[r] = min(farR[r], l);
    }

    // --- 2) Tính mxS và sufE ---
    // mxS[i] = max_{j <= i} farL[j]
    // sufE[i] = min_{j >= i} farR[j]
    vi mxS(n+2, 0), sufE(n+2, n+1);
    for(int i = 1; i <= n; i++){
        mxS[i] = max(mxS[i-1], farL[i]);
    }
    for(int i = n; i >= 1; i--){
        sufE[i] = min(sufE[i+1], farR[i]);
    }

    // --- 3) Xây nextS và nextE ---
    // nextS[i] = first-uncovered = mxS[i] + 1
    // nextE[i] = first-uncovered từ phải = sufE[i] - 1
    vi nextS(n+2), nextE(n+2);
    for(int i = 1; i <= n; i++){
        nextS[i] = min(n+1, mxS[i] + 1);
        nextE[i] = max(0,    sufE[i] - 1);
    }
    nextS[n+1] = n+1;
    nextE[0]   = 0;

    // --- 4) Build sparse-table (doubling) ---
    int LOG = lg2(n+1) + 1;
    vector<vi> jumpS(LOG, vi(n+2)), jumpE(LOG, vi(n+2));

    // cấp 0
    for(int i = 0; i <= n+1; i++){
        jumpS[0][i] = nextS[i];
        jumpE[0][i] = nextE[i];
    }
    // cấp k>0
    for(int k = 1; k < LOG; k++){
        for(int i = 0; i <= n+1; i++){
            jumpS[k][i] = jumpS[k-1][ jumpS[k-1][i] ];
            jumpE[k][i] = jumpE[k-1][ jumpE[k-1][i] ];
        }
    }

    // --- 5) Xử lý mỗi query ---
    while(q--){
        int S, E;
        cin >> S >> E;

        // Điều kiện căn bản: có curtain bắt đầu che S? có curtain kết thúc che E?
        if(mxS[S] < S || sufE[E] > E){
            cout << "NO\n";
            continue;
        }

        // --- Con trỏ từ trái (S) ---
        int curS = S;
        // nhảy các 2^k bước sao cho vẫn chưa vượt E
        for(int k = LOG-1; k >= 0; k--){
            int nxt = jumpS[k][curS];
            if(nxt <= E){
                curS = nxt;
            }
        }
        // sau cùng, vị trí được phủ tận cùng từ bên S:
        int X = mxS[curS];

        // --- Con trỏ từ phải (E) ---
        int curE = E;
        // nhảy các 2^k bước sao cho vẫn chưa trước S
        for(int k = LOG-1; k >= 0; k--){
            int nxt = jumpE[k][curE];
            if(nxt >= S){
                curE = nxt;
            }
        }
        // sau cùng, vị trí được phủ tận cùng từ bên E:
        int Y = sufE[curE];

        // Nếu hai “giao nhau” hoặc trùng nhau, tức Y <= X, thì có cách ghép kín [S..E]
        cout << (Y <= X ? "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