Submission #1150017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150017		VMaksimoski008	Curtains (NOI23_curtains)	C++20	100 / 100	714 ms	68576 KiB

curtains

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

struct segment_tree {
    int n;
    vector<int> tree, lazy;

    segment_tree(int _n) : n(_n), tree(4*n), lazy(4*n) {}

    void push(int u, int tl, int tr) {
        if(!lazy[u]) return ;
        tree[u] = max(tree[u], lazy[u]);

        if(tl != tr) {
            lazy[2*u] = max(lazy[2*u], lazy[u]);
            lazy[2*u+1] = max(lazy[2*u+1], lazy[u]);
        }

        lazy[u] = 0;
    }

    void U(int u, int tl, int tr, int l, int r) {
        push(u, tl, tr);
        if(tl > r || l > tr) return ;

        if(l <= tl && tr <= r) {
            lazy[u] = l;
            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        U(2*u, tl, tm, l, r);
        U(2*u+1, tm+1, tr, l, r);
        tree[u] = min(tree[2*u], tree[2*u+1]);
    }

    int Q(int u, int tl, int tr, int l, int r) {
        if(tl > r || l > tr) return 1e9;
        push(u, tl, tr);
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return min(Q(2*u, tl, tm, l, r), Q(2*u+1, tm+1, tr, l, r));
    }
};

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

    int n, m, q, l, r; cin >> n >> m >> q;

    vector<int> add[n+1];
    vector<pair<int, int> > qus[n+1];

    for(int i=1; i<=m; i++) {
        cin >> l >> r;
        add[r].push_back(l);
    }

    for(int i=1; i<=q; i++) {
        cin >> l >> r;
        qus[r].push_back({ l, i });
    }

    vector<int> ans(q+1);
    segment_tree sgt(n);
    for(r=1; r<=n; r++) {
        for(int l : add[r]) sgt.U(1, 1, n, l, r);
        for(auto [l, id] : qus[r])
            ans[id] = (sgt.Q(1, 1, n, l, r) >= l);
    }

    for(int i=1; i<=q; i++)
        cout << (ans[i] ? "YES" : "NO") << '\n';
}

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