#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> maxR(n+2, 0);
for(int i = 0; i < m; i++){
int l, r;
cin >> l >> r;
maxR[l] = max(maxR[l], r);
}
// 1) prefix max
vector<int> mx(n+2, 0);
for(int i = 1; i <= n; i++){
mx[i] = max(mx[i-1], maxR[i]);
}
// 2) build binary lifting
int LOG = 0;
while((1<<LOG) <= n) LOG++;
vector<vector<int>> nxt(LOG+1, vector<int>(n+2, n+1));
// nxt[0][i] = mx[i]
for(int i = 1; i <= n; i++){
nxt[0][i] = mx[i];
}
nxt[0][n+1] = n+1; // cột mốc out-of-bound
// dựng các mức k > 0
for(int k = 1; k <= LOG; k++){
for(int i = 1; i <= n+1; i++){
int reach = nxt[k-1][i];
int nextPos = min(n+1, reach + 1);
nxt[k][i] = nxt[k-1][ nextPos ];
}
}
// 3) xử lý truy vấn
while(q--){
int s, e;
cin >> s >> e;
// nếu ngay khởi đầu không thể mở màn
if(mx[s] < s){
cout << "NO\n";
continue;
}
int pos = s;
// cố gắng nhảy các bước 2^k lớn nhất sao cho chưa tới e
for(int k = LOG; k >= 0; k--){
int reach = nxt[k][pos];
if(reach < e){
pos = min(n+1, reach + 1);
}
}
// kiểm tra lần phủ sau cùng
if(nxt[0][pos] >= e) cout << "YES\n";
else cout << "NO\n";
}
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... |