Submission #1249749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249749		mr_fin	Curtains (NOI23_curtains)	C++20	9 / 100	1595 ms	2100 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;

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

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

    vector<pii> curtains(m);
    for(int i = 0; i < m; i++){
        cin >> curtains[i].first >> curtains[i].second;
    }
    // 1) Sắp xếp theo l tăng dần
    sort(curtains.begin(), curtains.end());

    while(q--){
        int s, e;
        cin >> s >> e;

        // 2) Tìm vị trí đầu tiên có l_i >= s
        int idx = int(lower_bound(curtains.begin(), curtains.end(),
                           make_pair(s, -1))
                      - curtains.begin());

        // max-heap chứa các r_i của curtains đã "đủ điều kiện" để mở rộng cur
        priority_queue<int> heap;
        int cur = s;
        bool ok = true;

        // 3) Greedy: mỗi bước lấy màn có r lớn nhất trong những màn có l <= cur
        while(cur <= e){
            // Đưa vào heap tất cả curtains[idx] có l <= cur
            while(idx < m && curtains[idx].first <= cur){
                if(curtains[idx].second <= e)
                    heap.push(curtains[idx].second);
                idx++;
            }
            // Nếu không có màn nào mở rộng được, thất bại
            if(heap.empty() || heap.top() < cur){
                ok = false;
                break;
            }
            // Lấy màn mở rộng xa nhất, gạt sang bên phải
            int bestR = heap.top(); 
            heap.pop();
            cur = bestR + 1;
        }

        cout << (ok ? "YES\n" : "NO\n");
    }

    return 0;
}

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