제출 #598101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598101		jhnah917	Event Hopping (BOI22_events)	C++14	100 / 100	198 ms	18888 KiB

events

#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 18, INF = 0x3f3f3f3f;

pair<int,int> T[SZ<<1];
pair<int,int> Query(int l, int r){
    l |= SZ; r |= SZ; pair<int,int> ret(INF,0);
    while(l <= r){
        if(l & 1) ret = min(ret, T[l++]);
        if(~r & 1) ret = min(ret, T[r--]);
        l >>= 1; r >>= 1;
    }
    return ret;
}

int N, K, Q, S[101010], E[101010], P[22][101010];
vector<int> C;
inline bool Check(int a, int b){ return S[b] <= E[a] && E[a] <= E[b]; }

int Solve(int a, int b){
    int ret = 0;
    if(a == b) return 0;
    for(int i=21; i>=0; i--) if(S[P[i][b]] > S[a]) b = P[i][b], ret |= 1 << i;
    if(ret + 1 == (1<<22)) return -1;
    if(E[a] > E[b]) return -1;
    if(Check(a, b)) return ret + 1;
    if(P[0][b] != 0 && Check(a, P[0][b])) return ret + 2;
    return -1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; C.reserve(N+N);
    for(int i=1; i<=N; i++) cin >> S[i] >> E[i], C.push_back(S[i]), C.push_back(E[i]);
    sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end()); K = C.size();
    for(int i=1; i<=N; i++){
        S[i] = lower_bound(C.begin(), C.end(), S[i]) - C.begin() + 1;
        E[i] = lower_bound(C.begin(), C.end(), E[i]) - C.begin() + 1;
    }

    fill(T, T+SZ*2, make_pair(INF,0));
    for(int i=1; i<=N; i++) T[E[i]|SZ] = min(T[E[i]|SZ], make_pair(S[i], i));
    for(int i=SZ-1; i; i--) T[i] = min(T[i<<1], T[i<<1|1]);
    for(int i=1; i<=N; i++) P[0][i] = Query(S[i], E[i]).second;
    for(int i=1; i<22; i++) for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];

    for(int q=1; q<=Q; q++){
        int a, b; cin >> a >> b;
        int res = Solve(a, b);
        if(res != -1) cout << res << "\n";
        else cout << "impossible\n";
    }
}

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