Submission #619511

#	Time	Username	Problem	Language	Result	Execution time	Memory
619511		Jomnoi	Event Hopping (BOI22_events)	C++17	100 / 100	191 ms	18148 KiB

events

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const int INF = 1e9 + 7;

int S[MAX_N], E[MAX_N];
int pre[MAX_N][20];

pair <int, int> tree[8 * MAX_N];

void build(int idx, int l, int r) {
    tree[idx] = make_pair(INF, INF);
    if(l == r) {
        return;
    }

    int mid = (l + r) / 2;
    build(idx * 2, l, mid);
    build(idx * 2 + 1, mid + 1, r);
}

void update(int idx, int l, int r, int q, pair <int, int> v) {
    if(l == r) {
        tree[idx] = min(tree[idx], v);
        return;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        update(idx * 2, l, mid, q, v);
    }
    else {
        update(idx * 2 + 1, mid + 1, r, q, v);
    }
    tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
}

pair <int, int> query(int idx, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return make_pair(INF, INF);
    }
    if(ql <= l and r <= qr) {
        return tree[idx];
    }

    int mid = (l + r) / 2;
    return min(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, M, Q;
    cin >> N >> Q;

    vector <int> vec;
    for(int i = 1; i <= N; i++) {
        cin >> S[i] >> E[i];

        vec.push_back(S[i]);
        vec.push_back(E[i]);
    }

    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    M = vec.size();

    for(int i = 1; i <= N; i++) {
        S[i] = lower_bound(vec.begin(), vec.end(), S[i]) - vec.begin() + 1;
        E[i] = lower_bound(vec.begin(), vec.end(), E[i]) - vec.begin() + 1;
    }

    build(1, 1, M);
    for(int i = 1; i <= N; i++) {
        update(1, 1, M, E[i], make_pair(S[i], i));
    }
    for(int i = 1; i <= N; i++) {
        auto [lm, nxt] = query(1, 1, M, S[i], E[i]);
        if(nxt != i and lm != S[i]) {
            pre[i][0] = nxt;
        }
    }
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= N; i++) {
            pre[i][j] = pre[pre[i][j - 1]][j - 1];
        }
    }

    while(Q--) {
        int s, e;
        cin >> s >> e;

        if(s == e) {
            cout << "0\n";
        }
        else if(E[s] > E[e]) {
            cout << "impossible\n";
        }
        else if(S[e] <= E[s] and E[s] <= E[e]) {
            cout << "1\n";
        }
        else {
            int ans = 2;
            for(int i = 19; i >= 0; i--) {
                if(pre[e][i] != 0 and E[s] < S[pre[e][i]]) {
                    e = pre[e][i];
                    ans += (1<<i);
                }
            }
            if(pre[e][0] != 0 and S[pre[e][0]] <= E[s]) {
                cout << ans << '\n';
            }
            else {
                cout << "impossible\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