Submission #1327818

#TimeUsernameProblemLanguageResultExecution timeMemory
1327818BolatuluCurtains (NOI23_curtains)C++20
100 / 100
727 ms87596 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define md ((tl + tr) >> 1)
#define TL v + v, tl, md
#define TR v + v + 1, md + 1, tr
#define F first
#define S second
#define pii pair<int, int>
#define int ll

const int maxn = 5e5 + 7;
const ll inf = 1e18 + 7;

struct tree{int suf; int mx;};

int n, m, q, l[maxn], r[maxn], s[maxn], e[maxn], ans[maxn];
tree t[4 * maxn];
vector<int> vq[maxn], vc[maxn];

tree merge(tree x, tree y) {
    if (x.suf == -1)
        return y;
    if (y.suf == -1)
        return x;

    tree res;
    res.mx = max(x.mx, y.mx);

    res.suf = y.suf;
    if (x.mx + 1 >= y.suf)
        res.suf = x.suf;
    return res;
}

void build(int v = 1, int tl = 1, int tr = n) {
    t[v].suf = tr + 1;
    t[v].mx = 0;
    if (tl == tr)
        return;
    build(TL), build(TR);
}

void upd(int p, int x, int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
        t[v].suf = tl;
        t[v].mx = max(t[v].mx, x);
        return;
    }
    if (p <= md)
        upd(p, x, TL);
    else
        upd(p, x, TR);
    t[v] = merge(t[v + v], t[v + v + 1]);
}

tree get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (tl >= l && tr <= r)
        return t[v];
    if (tl > r || l > tr)
        return {-1, -1};
    return merge(get(l, r, TL), get(l, r, TR));
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
        cin >> l[i] >> r[i];
    for (int i = 1; i <= q; i++)
        cin >> s[i] >> e[i];
    build();

    for (int i = 1; i <= m; i++)
        vc[r[i]].push_back(i);
    for (int i = 1; i <= q; i++)
        vq[e[i]].push_back(i);

    for (int i = 1; i <= n; i++) {
        for (auto j : vc[i])
            upd(l[j], r[j]);
        for (auto j : vq[i])
            ans[j] = get(s[j], e[j]).suf;
    }

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) {
        solve();
        // cout << '\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...