Submission #1249798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249798		mr_fin	Curtains (NOI23_curtains)	C++17	9 / 100	1592 ms	3044 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Curtain { int l, r; };

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

    int n, m, q;
    cin >> n >> m >> q;
    vector<Curtain> A(m);
    for(int i = 0; i < m; i++){
        cin >> A[i].l >> A[i].r;
    }
    // Sort globally by left endpoint to allow binary‐searching the start of l>=s
    sort(A.begin(), A.end(), [](auto &a, auto &b){
        return a.l < b.l;
    });

    while(q--){
        int s, e;
        cin >> s >> e;
        // 1) collect only intervals fully inside [s,e]
        //    i.e. l>=s && r<=e
        // 2) run the greedy cover check on [s,e]
        vector<pair<int,int>> segs;
        // find the first interval with l >= s
        auto it = lower_bound(A.begin(), A.end(), s,
            [](const Curtain &c, int x){ return c.l < x; }
        );
        // scan forward until l > e
        for(; it != A.end() && it->l <= e; ++it){
            if(it->r <= e){
                segs.emplace_back(it->l, it->r);
            }
        }
        // greedy cover:
        //   cur = s;
        //   while cur <= e, among all segs with l <= cur pick the one with max r
        //   move cur = max_r + 1
        int cur = s;
        size_t idx = 0;
        int bestR = s - 1;
        bool ok = true;
        // we assume segs is sorted by l already
        while(cur <= e){
            // extend bestR among all segs starting at or before cur
            while(idx < segs.size() && segs[idx].first <= cur){
                bestR = max(bestR, segs[idx].second);
                idx++;
            }
            if(bestR < cur){
                ok = false;
                break;
            }
            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