Submission #1283574

#TimeUsernameProblemLanguageResultExecution timeMemory
1283574petezaCurtains (NOI23_curtains)C++20
100 / 100
991 ms45872 KiB
#include <bits/stdc++.h>
using namespace std;
const int mxn = 500005;

int segm[mxn*4], laz[mxn*4];
int n, b, q, l, r;
int ans[mxn];

vector<pair<int, int>> qrs[mxn];

void push(int idx, int len) {
    segm[idx] = max(segm[idx], laz[idx]);
    if(len > 1) {
        laz[idx*2+1] = max(laz[idx*2+1], laz[idx]);
        laz[idx*2+2] = max(laz[idx*2+2], laz[idx]);
    }
    laz[idx] = 0;
}

void upd(int idx, int l, int r, int tl, int tr, int val) {
    push(idx, r-l+1);
    if(tr < l || r < tl) return;
    if(tl <= l && r <= tr) {
        laz[idx] = val;
        push(idx, r-l+1);
        return ;
    }
    int mid = (l+r) >> 1;
    upd(idx*2+1, l, mid, tl, tr, val);
    upd(idx*2+2, mid+1, r, tl, tr, val);
    segm[idx] = min(segm[idx*2+1], segm[idx*2+2]);
}

int qr(int idx, int l, int r, int tl, int tr) {
    push(idx, r-l+1);
    if(tr < l || r < tl) return INT_MAX;
    if(tl <= l && r <= tr) return segm[idx];
    int mid = (l+r) >> 1;
    return min(qr(idx*2+1, l, mid, tl, tr), qr(idx*2+2, mid+1, r, tl, tr));
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> b >> q;
    for(int i=1;i<=b;i++) {
        cin >> l >> r;
        qrs[r].emplace_back(-1, l);
    }
    for(int i=1;i<=q;i++) {
        cin >> l >> r;
        qrs[r].emplace_back(i, l);
    }
    for(int i=1;i<=n;i++) {
        sort(qrs[i].begin(), qrs[i].end());
        for(auto &e:qrs[i]) {
            if(e.first == -1) {
                upd(0, 1, n, e.second, i, e.second+1);
            } else {
                //for(int bruh = 1; bruh <= n; bruh++) cout << qr(0, 1, n, bruh, bruh) << ' '; 
                //cout << qr(0, 1, n, e.second, i) << '\n';
                ans[e.first] = (e.second < qr(0, 1, n, e.second, i));
            }
        }
    }
    for(int i=1;i<=q;i++) cout << (ans[i] ? "YES" : "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...