#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 time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |