제출 #1282908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282908		MisterReaper	Curtains (NOI23_curtains)	C++20	100 / 100	655 ms	69080 KiB

curtains

// File curtains.cpp created on 24.10.2025 at 11:39:59
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int inf = int(1E9);

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)

struct segtree {
    struct node {
        int mx = inf;
        int lz = inf;
        void modify(int x) {
            mx = std::min(mx, x);
            lz = std::min(mx, x);
        }
    };
    node unite(const node lhs, const node rhs) {
        node res;
        res.mx = std::max(lhs.mx, rhs.mx);
        return res;
    }
    int n;
    std::vector<node> tree;
    segtree(int n_) : n(n_), tree(n << 1) {}
    void push(int v, int l, int r) {
        def;
        tree[lv].modify(tree[v].lz);
        tree[rv].modify(tree[v].lz);
        tree[v].lz = inf;
    }
    void modify(int v, int l, int r, int ql, int qr, int x) {
        if (ql == l && r == qr) {
            tree[v].modify(x);
            return;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            modify(lv, l, mid, ql, qr, x);
        } else if (mid + 1 <= ql) {
            modify(rv, mid + 1, r, ql, qr, x);
        } else {
            modify(lv, l, mid, ql, mid, x);
            modify(rv, mid + 1, r, mid + 1, qr, x);
        }
        tree[v] = unite(tree[lv], tree[rv]);
    }
    void modify(int l, int r, int x) {
        modify(0, 0, n - 1, l, r, x);
    }
    node get(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v];
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            return get(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return get(rv, mid + 1, r, ql, qr);
        } else {
            return unite(get(lv, l, mid, ql, mid),
                        get(rv, mid + 1, r, mid + 1, qr));
        }
    }
    node get(int l, int r) {
        return get(0, 0, n - 1, l, r);
    }
};

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

    int N, M, Q;
    std::cin >> N >> M >> Q;

    std::vector<std::vector<int>> add(N);
    std::vector<std::array<int, 2>> A(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i][0] >> A[i][1];
        --A[i][0], --A[i][1];
        add[A[i][0]].emplace_back(A[i][1]);
    }

    std::vector<std::vector<int>> ask(N);
    std::vector<std::array<int, 2>> qry(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> qry[i][0] >> qry[i][1];
        --qry[i][0], --qry[i][1];
        ask[qry[i][0]].emplace_back(i);
    }

    segtree seg(N);
    std::vector<int> ans(Q);
    for (int i = N - 1; i >= 0; --i) {
        for (auto j : add[i]) {
            seg.modify(i, j, j);
        }
        for (auto j : ask[i]) {
            ans[j] = seg.get(i, qry[j][1]).mx <= qry[j][1];
        }
    }

    for (int i = 0; i < Q; ++i) {
        std::cout << (ans[i] ? "YES" : "NO") << '\n';
    }

    return 0;
}

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