Submission #1331254

#TimeUsernameProblemLanguageResultExecution timeMemory
1331254Canuc80kCurtains (NOI23_curtains)C++20
100 / 100
630 ms74896 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e6 + 1;

struct STN {
    ll val, lazy;
};
struct SegmentTree {
    STN st[N * 4 + 100];
    STN merge(STN a, STN b) {
        return {min(a.val, b.val), 0};
    }
    void down(ll id) {
        if (st[id].lazy != 0) {
            ll val = st[id].val;
            st[id << 1].val = max(st[id << 1].val, val);
            st[id << 1 | 1].val = max(st[id << 1 | 1].val, val);

            st[id << 1].lazy = max(st[id << 1].lazy, val);
            st[id << 1 | 1].lazy = max(st[id << 1 | 1].lazy, val);

            st[id].lazy = 0;
        }
    }
    void update(ll id, ll l, ll r, ll u, ll v, ll val) {
        if (r < u || l > v) return;
        if (u <= l && r <= v) {
            st[id].val = max(st[id].val, val);
            st[id].lazy = val;
            return;
        }
        down(id);
        ll mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = merge(st[id << 1], st[id << 1 | 1]);
    }
    void update(ll l, ll r, ll val) {
        update(1, 1, 1e6, l, r, val);
    }

    STN get(ll id, ll l, ll r, ll u, ll v) {
        if (r < u || l > v) return {(ll)1e18, 0};
        if (u <= l && r <= v) {
            // cout << "__ " << id << ' ' << l << ' ' << r << endl;
            return st[id];
        }
        down(id);
        ll mid = (l + r) >> 1;
        return merge(
            get(id << 1, l, mid, u, v),
            get(id << 1 | 1, mid + 1, r, u, v)
        );
    }
    STN get(ll l, ll r) {
        return get(1, 1, 1e6, l, r);
    }
};

ll n, m, q;
ll a[N], finalRes[N];
vector<ll> curts[N];
vector<array<ll, 2>> query[N];
SegmentTree st;

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

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i ++) {
        ll l, r; cin >> l >> r;
        curts[r].push_back(l);
    }
    for (int i = 1; i <= q; i ++) {
        ll l, r; cin >> l >> r;
        query[r].push_back({l, i});
    }

    for (int r = 1; r <= 5e5; r ++) {
        for (auto l: curts[r]) {
            st.update(l, r, l);
        }
        for (auto [l, i]: query[r]) {
            // cout << "???: " << endl << st.get(l, r).val << endl;
            if (st.get(l, r).val >= l) finalRes[i] = 1;
            else finalRes[i] = 0;
        }
    }

    for (int i = 1; i <= q; i ++) {
        if (finalRes[i] == 1) cout << "YES\n";
        else cout << "NO\n";
    }
}
#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...