#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
vector<int> tree;
vector<bool> lazy;
void push(int v) {
if (!lazy[v]) return;
lazy[v] = 0;
if (tree[v] < tree[2*v]) {
lazy[2*v] = 1;
tree[2*v] = tree[v];
}
if (tree[v] < tree[2*v+1]) {
lazy[2*v+1] = 1;
tree[2*v+1] = tree[v];
}
}
void update(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return;
if (tl == l && tr == r) {
if (x >= tree[v]) return;
tree[v] = x;
lazy[v] = 1;
return;
}
int tm = (tl+tr)/2;
update(2*v, tl, tm, l, min(r, tm), x);
update(2*v+1, tm+1, tr, max(l, tm+1), r, x);
tree[v] = max(tree[2*v], tree[2*v+1]);
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return INT32_MIN;
if (tl == l && tr == r) return tree[v];
push(v);
int tm = (tl+tr)/2;
int a = query(2*v, tl, tm, l, min(r, tm));
int b = query(2*v+1, tm+1, tr, max(l, tm+1), r);
return max(a, b);
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
tree.resize(4*n, INT32_MAX);
lazy.resize(4*n, false);
vector<pair<int, int>> seg;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
seg.push_back({a, b});
}
sort(seg.begin(), seg.end());
vector<int> mn(n, INT32_MAX);
vector<ppi> queries;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
queries.push_back({{a, b}, i});
}
sort(queries.begin(), queries.end());
vector<string> res(q);
while (!queries.empty()) {
pi p;
int a, b, idx;
tie(p, idx) = queries.back();
tie(a, b) = p;
queries.pop_back();
while (!seg.empty() && seg.back().first >= a) {
int aa, bb;
tie(aa, bb) = seg.back();
seg.pop_back();
update(1, 0, n-1, aa, bb, bb);
}
int mx = query(1, 0, n-1, a, b);
res[idx] = (mx <= b) ? "YES" : "NO";
}
for (const auto& ans : res) {
cout << ans << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# | 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... |