Submission #1176018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176018		quannd	Event Hopping (BOI22_events)	C++20	0 / 100	48 ms	25780 KiB

events

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pii pair<int,int>
 
// Số bước nhảy tối đa (với n <= 1e5, log2(1e5) < 20)
const int LIM = 20;
 
int n, q;
pii a[100005]; // Lưu các đoạn, sau sắp theo r tăng dần
// pos[ id ban đầu ] = vị trí của đoạn đó sau khi sắp (1-indexed)
int pos[100005];
 
// jump[i][k]: từ vị trí i trong mảng sắp, sau 2^k bước nhảy ngược, ta được vị trí nào.
int jump[100005][25];
 
// Hàm so sánh: sắp theo r tăng dần; nếu r bằng, sắp theo l tăng dần.
bool cmp(pii x, pii y){
    if(x.second == y.second) return x.first < y.first;
    return x.second < y.second;
}
 
// Ta xây dựng jump[i][0]:
// Từ vị trí i (i>=2) ta có thể nhảy về i-1 nếu thỏa điều kiện: l của a[i] <= r của a[i-1].
// Với i==1, không có ai phía trước.
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    // Lưu các đoạn kèm id ban đầu (chỉ số từ 1 đến n)
    vector< pair<pii,int> > segs;
    for (int i = 1; i <= n; i++){
        int l, r;
        cin >> l >> r;
        segs.push_back({{l, r}, i});
    }
    
    // Sắp theo r tăng dần (nếu r bằng thì theo l)
    sort(segs.begin(), segs.end(), [&](auto A, auto B){
        if(A.first.second == B.first.second) return A.first.first < B.first.first;
        return A.first.second < B.first.second;
    });
    
    // Gán lại mảng a[] theo thứ tự sắp và lưu pos
    for (int i = 0; i < n; i++){
        a[i+1] = segs[i].first; // a[1..n]
        pos[segs[i].second] = i+1; // vị trí của đoạn có id ban đầu = segs[i].second
    }
    
    // Xây dựng jump[i][0]
    // Với i = 1: không có đoạn phía trước, nên jump[1][0] = 0.
    jump[1][0] = 0;
    for (int i = 2; i <= n; i++){
        // Kiểm tra điều kiện: từ a[i] (đích) thì có thể "nhảy ngược" từ i về i-1 nếu:
        // a[i].first (l của a[i]) <= a[i-1].second (r của a[i-1])
        if(a[i].first <= a[i-1].second)
            jump[i][0] = i - 1;
        else
            jump[i][0] = 0;
    }
    
    // Xây dựng bảng binary lifting
    for (int k = 1; k <= LIM; k++){
        for (int i = 1; i <= n; i++){
            int prev = jump[i][k-1];
            if(prev == 0) jump[i][k] = 0;
            else jump[i][k] = jump[prev][k-1];
        }
    }
    
    // Trả lời truy vấn:
    // Ý tưởng: cho truy vấn (x, y) theo chỉ số ban đầu.
    // Chuyển sang vị trí trong mảng sắp: u = pos[x], v = pos[y].
    // Vì chuỗi chuyển động của chúng ta là "nhảy ngược" (giảm chỉ số),
    // để có thể đi từ x đến y, ta cần u >= v.
    // Sau đó, dùng binary lifting để tìm số bước tối thiểu chuyển từ u về v.
    for (int i = 1; i <= q; i++){
        int X, Y;
        cin >> X >> Y;
        int u = pos[X], v = pos[Y];
        if(u < v){
            cout << "impossible" << "\n";
            continue;
        }
        // Nếu u == v, nghĩa là x và y là cùng một đoạn sau sắp.
        if(u == v){
            cout << 0 << "\n";
            continue;
        }
        
        int steps = 0;
        int cur = u;
        // Dùng binary lifting: cố gắng nhảy càng xa về phía đầu (giảm chỉ số)
        for (int k = LIM; k >= 0; k--){
            int nxtPos = jump[cur][k];
            // Nếu có thể nhảy và vẫn chưa vượt quá v (tức vẫn >= v)
            if(nxtPos != 0 && nxtPos >= v){
                cur = nxtPos;
                steps += (1LL << k);
            }
        }
        // Sau khi dùng binary lifting, ta cần kiểm tra xem đã đạt đúng vị trí v hay chưa.
        if(cur == v) cout << steps << "\n";
        else cout << "impossible" << "\n";
    }
    
    return 0;
}

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