제출 #1325853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325853		edo	Event Hopping (BOI22_events)	C++20	100 / 100	103 ms	23104 KiB

events

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define no "impossible\n"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // --s1-------e1------
    // -----s2-------e2---
    // --s3------e3-------
    // -------s4-------e4-
    int N, Q;
    cin >> N >> Q;
    vector<pair<int, int>> a(N);
    vector<int> b;
    for(int i = 0; i < N; i++) {
        cin >> a[i].first >> a[i].second;
        b.push_back(a[i].second);
    }
    ranges::sort(b);
    b.erase(unique(b.begin(), b.end()), b.end());
    const int LOG = 17;
    const int inf = 1e9 + 5;
    vector rmq(LOG, vector<pair<int, int>>(N, {inf, -1}));
    for(int i = 0; i < N; i++) {
        int r = ranges::lower_bound(b, a[i].second) - b.begin();
        rmq[0][r] = min(rmq[0][r], {a[i].first, i});
    }

    for(int i = 0; i + 1 < LOG; i++) 
        for(int j = 0; j + (1 << (i + 1)) <= N; j++) 
            rmq[i + 1][j] = min(rmq[i][j], rmq[i][j + (1 << i)]);

    vector up(LOG, vector<int>(N));
    for(int i = 0; i < N; i++) {
        int l = ranges::lower_bound(b, a[i].first) - b.begin();
        int r = ranges::lower_bound(b, a[i].second) - b.begin();
        int h = __lg(r - l + 1);
        up[0][i] = min(rmq[h][l], rmq[h][r + 1 - (1 << h)]).second;
    }

    for(int i = 0; i + 1 < LOG; i++) 
        for(int j = 0; j < N; j++) 
            up[i + 1][j] = up[i][up[i][j]];

    while(Q--) {
        int s, e;
        cin >> s >> e, s--, e--;
        int l = 1;
        if(s == e || a[e].first <= a[s].second && a[s].second <= a[e].second) {
            cout << (s == e ? 0 : 1) << "\n";
            continue;
        }

        for(int i = LOG; i--;) {
            if(a[s].second < a[up[i][e]].first) 
                l += 1 << i, e = up[i][e];
        }

        e = up[0][e];
        if(a[s].second < a[e].first || a[s].second > a[e].second) 
            cout << no;
        else 
            cout << l + (a[s].second >= a[e].first) << "\n";
    }


    return 0;
}

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