제출 #1172975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172975		nguyenkhangninh99	Event Hopping (BOI22_events)	C++20	0 / 100	116 ms	79164 KiB

events

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pii pair<int, int>

const int maxn = 2e5 + 5;

int a[maxn], b[maxn], pre[19][maxn];
pii st[19][maxn];

void solve(){
    int n, q; cin >> n >> q;

    vector<int> compress;

    for (int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        compress.push_back(a[i]);
        compress.push_back(b[i]);
    }

    sort(compress.begin(), compress.end());
    compress.resize(unique(compress.begin(), compress.end()) - compress.begin());

    for (int i = 0; i < 19; i++){
        for (int j = 1; j <= compress.size(); j++){
            st[i][j] = {1e18, 1e18};
        }
    }

    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin() + 1,
        b[i] = lower_bound(compress.begin(), compress.end(), b[i]) - compress.begin() + 1,
        st[0][b[i]] = min(st[0][b[i]], {a[i], i});
    }


    for (int i = 1; i < 19; i++){
        for (int j = 1; j + (1 << i) - 1 <= compress.size(); j++){
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        }
    }

    for (int i = n; i >= 1; i--){
        int k = __lg(b[i] - a[i] + 1);
        pre[0][i] = min(st[k][a[i]], st[k][b[i] - (1 << k) + 1]).se;
    }
    for (int i = 1; i < 19; i++){
        for (int j = 1; j <= n; j++) pre[i][j] = pre[i - 1][pre[i - 1][j]];
    }

    while(q--){
        int u, v; cin >> u >> v;
        if (u == v) cout << 0 << "\n";
        else if (b[u] > b[v]) cout << -1 << "\n";
        else if (a[v] <= b[u] && b[u] <= b[v]) cout << 1 << "\n";

        else{
            int ans = 0;
            int cur = v;
            for (int j = 18; j >= 0; j--){
                if (a[pre[j][cur]] > b[u]){
                    ans += 1 << j;
                    cur = pre[j][cur];
                }
            }
                
            if (a[pre[0][cur]] <= b[u]) cout << ans + 2 << "\n";
            else cout << "impossible\n";
        }
    }

}


 
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
 
 
    solve();
}

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