#include <bits/stdc++.h>
using namespace std;
struct Node {
int l, r;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<Node> nodes(N);
vector<int> compVals;
for (int i = 0; i < N; i++){
cin >> nodes[i].l >> nodes[i].r;
compVals.push_back(nodes[i].l);
compVals.push_back(nodes[i].r);
}
// Coordinate compression
sort(compVals.begin(), compVals.end());
compVals.erase(unique(compVals.begin(), compVals.end()), compVals.end());
auto comp = [&](int x) -> int {
return int(lower_bound(compVals.begin(), compVals.end(), x) - compVals.begin());
};
// Sắp xếp các nút theo l để dễ truy vấn "cho x, tìm max r"
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b){
return nodes[a].l < nodes[b].l;
});
// LOG: số lớp binary lifting (số bước nhảy tối đa giả sử)
const int LOG = 20;
// Với mỗi truy vấn, ta sẽ xây dựng hàm f chỉ với các nút có r <= r_b của truy vấn đó.
// Hàm f: với một giá trị hiện tại (đã nén) x, trả về giá trị max { comp(nodes[i].r) }
// với các nút i thỏa nodes[i].l <= compVals[x] và nodes[i].r <= r_b.
for (int qi = 0; qi < Q; qi++){
int a, b;
cin >> a >> b;
a--; b--; // chuyển về 0-indexed
if(a == b){
cout << 0 << "\n";
continue;
}
int Ra = nodes[a].r, Rb = nodes[b].r, Lb = nodes[b].l;
// Nếu không thoả điều kiện cần thiết để có đường đi (do r chỉ tăng)
if(Ra > Rb){
cout << "impossible\n";
continue;
}
// Nếu có thể chuyển trực tiếp từ a đến b (vì r_a >= l_b)
if(Ra >= Lb){
cout << 1 << "\n";
continue;
}
// Xây dựng mảng F cho hàm f, trên không gian các giá trị đã nén.
// F[i] = giá trị lớn nhất (đã nén) của nodes[j].r với các nút có
// nodes[j].l <= compVals[i] và nodes[j].r <= Rb.
int m = compVals.size();
vector<int> F(m, -1);
// Duyệt theo thứ tự tăng của l (đã được sắp xếp trong order)
for (int idx : order) {
if(nodes[idx].r <= Rb){
int pos = comp(nodes[idx].l);
int rpos = comp(nodes[idx].r);
F[pos] = max(F[pos], rpos);
}
}
// Xây dựng tiền xử lý "prefix max" trên F:
for (int i = 1; i < m; i++){
F[i] = max(F[i], F[i - 1]);
}
// Hàm f: cho trạng thái hiện tại x (đã nén), trả về F[x].
auto f_func = [&](int x) -> int {
return F[x];
};
int start = comp(Ra);
int goal = comp(Lb);
// Nếu giá trị ban đầu đã vượt qua goal (nghĩa là có thể chuyển trực tiếp)
if(start >= goal){
cout << 1 << "\n";
continue;
}
// Xây dựng bảng binary lifting cho hàm f.
vector<vector<int>> dp(LOG, vector<int>(m, 0));
for (int i = 0; i < m; i++){
dp[0][i] = f_func(i);
}
for (int k = 1; k < LOG; k++){
for (int i = 0; i < m; i++){
dp[k][i] = dp[k - 1][ dp[k - 1][i] ];
}
}
// Sử dụng binary lifting để nhảy từ start đến vị trí có giá trị >= goal
int cur = start;
int ans = 0;
for (int k = LOG - 1; k >= 0; k--){
if(dp[k][cur] < goal){
cur = dp[k][cur];
ans += (1 << k);
}
}
// Bước nhảy cuối cùng
if(f_func(cur) >= goal){
cout << ans + 2 << "\n";
} else {
cout << "impossible\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... |