제출 #1353178

#제출 시각아이디문제언어결과실행 시간메모리
1353178Desh03Curtains (NOI23_curtains)C++20
100 / 100
479 ms59228 KiB
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

struct ST {
    vector<int> st, lz;
    int n;
    ST(int n) : n(n) {
        while (n & n - 1) ++n;
        st.resize(n << 1, -1), lz.resize(n << 1, -1);
    }
    void push(int v) {
        st[v << 1] = max(st[v << 1], lz[v]);
        st[v << 1 | 1] = max(st[v << 1 | 1], lz[v]);
        lz[v << 1] = max(lz[v << 1], lz[v]);
        lz[v << 1 | 1] = max(lz[v << 1 | 1], lz[v]);
        lz[v] = -1;
    }
    void upd(int v, int l, int r, int ql, int qr, int x) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            st[v] = max(st[v], x);
            lz[v] = max(lz[v], x);
            return;
        }
        if (lz[v] != -1) push(v);
        int m = l + r >> 1;
        upd(v << 1, l, m, ql, qr, x);
        upd(v << 1 | 1, m + 1, r, ql, qr, x);
        st[v] = min(st[v << 1], st[v << 1 | 1]);
    }
    int qry(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return inf;
        if (l >= ql && r <= qr) return st[v];
        if (lz[v] != -1) push(v);
        int m = l + r >> 1;
        return min(qry(v << 1, l, m, ql, qr), qry(v << 1 | 1, m + 1, r, ql, qr));
    }
    int qry(int l, int r) {
        return qry(1, 0, n - 1, l, r);
    }
    void upd(int l, int r, int x) {
        upd(1, 0, n - 1, l, r, x);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> ls(n);
    while (m--) {
        int l, r;
        cin >> l >> r;
        ls[--r].push_back(--l);
    }
    vector<vector<pair<int, int>>> qr(n);
    for (int i = 0; i < q; i++) {
        int s, e;
        cin >> s >> e;
        qr[--e].push_back({--s, i});
    }
    ST st(n);
    vector<bool> ans(q);
    for (int i = 0; i < n; i++) {
        for (int l : ls[i]) {
            st.upd(l, i, l);
        }
        for (auto [s, j] : qr[i]) {
            ans[j] = (st.qry(s, i) >= s);
        }
    }
    for (int i = 0; i < q; i++) {
        cout << (ans[i] ? "YES" : "NO") << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...