제출 #1124431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124431		ShadowShark	Curtains (NOI23_curtains)	C++20	100 / 100	1122 ms	28196 KiB

curtains

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

const int maxN = 5e5 + 5;
int n, m, q;
pair<int, int> seg[maxN];

namespace ac {
    struct node {
        int val, lazy;
    } st[4 * maxN];


    void down(int id) {
        st[2 * id].val = max(st[2 * id].val, st[id].lazy);
        st[2 * id].lazy = max(st[2 * id].lazy, st[id].lazy);

        st[2 * id + 1].val = max(st[2 * id + 1].val, st[id].lazy);
        st[2 * id + 1].lazy = max(st[2 * id + 1].lazy, st[id].lazy);

        st[id].lazy = 0;
    }

    void update(int id, int l, int r, int u, int v, int val) {
        if (v < l || r < u) return ;

        if (u <= l && r <= v) {
            st[id].val = max(st[id].val, val);
            st[id].lazy = max(st[id].lazy, val);
            return ;
        }

        int mid = (l + r) >> 1;
        down(id);

        update(2 * id, l, mid, u, v, val);
        update(2 * id + 1, mid + 1, r, u, v, val);

        st[id].val = min(st[2 * id].val, st[2 * id + 1].val);
    }

    int get(int id, int l, int r, int u, int v) {
        if (v < l || r < u) return 1e9;

        if (u <= l && r <= v) return st[id].val;

        int mid = (l + r) >> 1;
        down(id);

        int A = get(2 * id, l, mid, u, v);
        int B = get(2 * id + 1, mid + 1, r, u, v);

        return min(A, B);
    }

    struct qr {
        int l, r, id;

        bool operator < (const qr& rhs) const {
            if (r != rhs.r) return r < rhs.r;
            return id < rhs.id;
        }
    } query[2 * maxN];
    int res[maxN];

    void solve() {
        int cnt_query = 0;

        for (int i = 1; i <= m; i++)
            query[++cnt_query] = {seg[i].first, seg[i].second, 0};

        for (int i = 1; i <= q; i++) {
            int u, v;
            cin >> u >> v;

            query[++cnt_query] = {u, v, i};
        }

        sort(query + 1, query + cnt_query + 1);

        for (int i = 1; i <= cnt_query; i++) {
            auto [l, r, id] = query[i];

            if (id == 0) update(1, 1, n, l, r, l);
                else {
                    int x = get(1, 1, n, l, r);
                    res[id] = (x == l);
                }
        }

        for (int i = 1; i <= q; i++) {
            if (res[i]) cout << "YES\n";
                else cout << "NO\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("curtains.inp", "r", stdin);
    //freopen("curtains.out", "w", stdout);

    cin >> n >> m >> q;

    for (int i = 1; i <= m; i++)
        cin >> seg[i].first >> seg[i].second;

    ac::solve();

    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