제출 #1132147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132147		lopkus	Curtains (NOI23_curtains)	C++20	9 / 100	54 ms	28996 KiB

curtains

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5e5 + 5;

struct seg_tree{
    int t[4* N];
    void reset() {
        for(int i = 0; i < 4 * N; i++) {
            t[i] = 1e18;
        }
        return;
    }
    int lazy[4 * N] = {0};
    void propagate(int v) {
        int lc = v * 2;
        int rc = v * 2 + 1;
        t[lc] = max(t[lc], lazy[v]);
        t[rc] = max(t[rc], lazy[v]);
        lazy[lc] = max(lazy[lc], lazy[v]);
        lazy[rc] = max(lazy[rc], lazy[v]);
        t[v] = max(t[v], lazy[v]);
    }
    int query(int v, int tl, int tr, int l, int r) {
        if(tl > r || tr < l || tl > tr) {
            return 1e18;
        }
        if(tl >= l && tr <= r) {
            return t[v];
        }
        propagate(v);
        int tm = (tl + tr) / 2;
        return min(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
    }
    void update(int v, int tl, int tr, int l, int r, int x) {
        if(tl > r || tr < l || tl > tr) {
            return;
        }
        if(tl >= l && tr <= r) {
            lazy[v] = max(lazy[v], x);
            t[v] = max(t[v], x);
            return;
        }
        propagate(v);
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, l, r, x);
        update(v * 2 + 1, tm + 1, tr, l, r, x);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
}seg;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> l(m + 1);
    vector<int> r(m + 1);
    vector<int> update[n + 1];
    for(int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i];
        update[r[i]].push_back(l[i]);
    }
    vector<pair<int,int>> queries[n + 1];
    for(int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        queries[y].push_back({x, i});
    }
    vector<int> ans(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        sort(update[i].begin(), update[i].end());
        sort(queries[i].begin(), queries[i].end());
        for(auto it : update[i]) {
            /*
            for(int j = it; j <= i; j++) {
                c[j] = max(c[j], it);
            }*/
            seg.update(1, 1, n, it, i, it);
        }
        for(auto it : queries[i]) {
            /*
            int ok = n + 1;
            for(int j = it.first; j <= i; j++) {
                ok = min(ok, c[j]);
            }
            if(ok >= it.first) {
                ans[it.second] = 1;
            }*/
            if(seg.query(1, 1, n, it.first, i) >= it.first) {
                ans[it.second] = 1;
            }
        }
    }
    for(int i = 1; i <= q; i++) {
        cout << (ans[i]? "YES\n":"NO\n");
    }
}

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