Submission #1249811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249811		mr_fin	Curtains (NOI23_curtains)	C++17	0 / 100	1525 ms	18164 KiB

curtains

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

// --- segment tree supporting point‐update max and prefix‐max query ---
struct SegTree {
    int n;
    vector<int> st;
    SegTree(int _n): n(_n), st(4*n+4, 0) {}
    void update(int p, int val, int idx=1, int l=1, int r=-1) {
        if (r<0) r = n;
        if (l==r) {
            st[idx] = max(st[idx], val);
            return;
        }
        int mid = (l+r)>>1;
        if (p <= mid) update(p, val, idx<<1, l, mid);
        else          update(p, val, idx<<1|1, mid+1, r);
        st[idx] = max(st[idx<<1], st[idx<<1|1]);
    }
    // return max over [L..R]
    int query(int L, int R, int idx=1, int l=1, int r=-1) {
        if (r<0) r = n;
        if (R < l || r < L)       return 0;
        if (L <= l && r <= R)     return st[idx];
        int mid = (l+r)>>1;
        return max(
            query(L, R, idx<<1, l, mid),
            query(L, R, idx<<1|1, mid+1, r)
        );
    }
};

struct Curtain { int l, r; };
struct Query   { int s, e, idx; };

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;

    vector<Query> Q(q);
    for (int i = 0; i < q; i++) {
        cin >> Q[i].s >> Q[i].e;
        Q[i].idx = i;
    }

    // sort curtains by r ascending
    sort(A.begin(), A.end(),
         [](auto &a, auto &b){ return a.r < b.r; });

    // sort queries by e ascending
    vector<Query> byE = Q;
    sort(byE.begin(), byE.end(),
         [](auto &a, auto &b){ return a.e < b.e; });

    SegTree st(n);
    vector<bool> ans(q);
    int p = 0;
    for (auto &qj : byE) {
        // add all curtains with r <= qj.e
        while (p < m && A[p].r <= qj.e) {
            st.update(A[p].l, A[p].r);
            p++;
        }
        // greedy cover [s..e]
        int cur = qj.s;
        bool ok = true;
        while (cur <= qj.e) {
            int bestR = st.query(1, cur);
            if (bestR < cur) {
                ok = false;
                break;
            }
            cur = bestR + 1;
        }
        ans[qj.idx] = ok;
    }

    // output in original order
    for (int i = 0; i < q; i++)
        cout << (ans[i] ? "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