Submission #1176121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176121		quannd	Event Hopping (BOI22_events)	C++20	10 / 100	1594 ms	19644 KiB

events

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30