Submission #862786

#	Time	Username	Problem	Language	Result	Execution time	Memory
862786		adhityamv	Event Hopping (BOI22_events)	C++17	0 / 100	331 ms	19924 KiB

events

#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define oo 1e9
 
using namespace std;
 
struct DATA{
    int mn = oo, id;
};
 
const int MAX = 1e5 + 5, LOGMAX = 20;
int n, q;
 
pii arr[MAX];
pii tree[8 * MAX];
 
DATA comb(DATA a, DATA b){
    if(a.mn < b.mn){
        return a;
    }
    else{
        return b;
    }
}
 
void update(int node, int l, int r, int pos, int val, int id){
    if(l == r){
        tree[node] = {val, id};
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        update(2 * node, l, mid, pos, val, id);
    }
    else{
        update(2 * node + 1, mid + 1, r, pos, val, id);
    }
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
 
pii ask(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql) return mp(1000000001,-1);
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return min(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}
 
void compress(){
    vector<pii> v;
    for(int i = 1; i <= n; i++){
        v.push_back({arr[i].first, i});
        v.push_back({arr[i].second, -i});
    }
    sort(v.begin(), v.end());
    int t = 0;
    for(int i = 0; i < 2 * n; i++){
        if(i == 0 || v[i].first != v[i - 1].first){
            t++;
        }
        if(v[i].second > 0){
            arr[v[i].second].first = t;
        }
        else{
            arr[-v[i].second].second = t;
        }
    }
}
 
int par[LOGMAX][MAX];
 
bool isReachable(int i, int j){
    return arr[j].first <= arr[i].second && arr[i].second <= arr[j].second;
}
 
int lift(int s, int d){
    int res = 2;
    if(isReachable(s, d)){
        return 1;
    }
    for(int i = LOGMAX - 1; i >= 0; i--){
        if(!isReachable(s, par[i][d]) && arr[par[i][d]].second >= arr[s].second){
            d = par[i][d];
            res += (1 << i);
        }
    }
    if(!isReachable(s, par[0][d])){
        return -1;
    }
    return res;
}
 
int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> arr[i].first >> arr[i].second;
    }
    compress();
    for(int i = 1; i <= n; i++){
        update(1, 1, 2 * n, arr[i].second, arr[i].first, i);
    }
    for(int i = 1; i <= n; i++){
        par[0][i] = ask(1, 1, 2 * n, arr[i].first, arr[i].second).second;
    }
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
 
    while(q--){
        int s, d; cin >> s >> d;
        if(s == d){
            cout << "0\n";
            continue;
        }
        int ans = lift(s, d);
        if(ans == -1){
            cout << "impossible\n";
        }
        else{
            cout << ans << '\n';
        }
    }
}

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