Submission #634379

#	Time	Username	Problem	Language	Result	Execution time	Memory
634379		dooompy	Event Hopping (BOI22_events)	C++17	100 / 100	405 ms	20248 KiB

events

#include <bits/stdc++.h>

using namespace std;

int s[200005], e[200005];

vector<int> comp;

pair<int, int> tree[4 * 200005];

void update(int x, int l, int r, int loc, pair<int, int> stuff) {
    if (l == r) {
        tree[x] = min(tree[x], stuff);
        return;
    }

    int mid = (l + r) / 2;

    if (loc <= mid) update(2 * x, l, mid, loc, stuff);
    else update(2 * x + 1, mid + 1, r, loc, stuff);

    tree[x] = min(tree[2 * x], tree[2 * x + 1]);
}

int convert(int x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
}

int prevjmp[100005][20];

pair<int, int> get(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[x];
    if (l > qr || r < ql) return {1e9 + 10, 1e9 + 10};

    int mid = (l + r) / 2;

    return min(get(2 * x, l, mid, ql, qr), get(2 * x + 1, mid + 1, r, ql, qr));
}

int main() {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> e[i];
        comp.push_back(s[i]);
        comp.push_back(e[i]);
    }

    fill(&tree[0], &tree[0] + sizeof(tree) / sizeof(tree[0]), make_pair(1e9 + 10, 1e9 + 10));

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

    int sz = comp.size();

    for (int i = 1; i <= n; i++) {
        // find furtherst cano back
        s[i] = convert(s[i]);
        e[i] = convert(e[i]);

        update(1, 1, sz, e[i], {s[i], i});
    }

    for (int i = 1; i <= n; i++) {
        prevjmp[i][0] = get(1, 1, sz, s[i], e[i]).second;
    }

    for (int log = 1; log < 20; log++) {
        for (int i = 1; i <= n; i++) {
            prevjmp[i][log] = prevjmp[prevjmp[i][log-1]][log-1];
        }
    }


    for (int i = 0; i < q; i++) {
        long long ans = 0;
        int a, b; cin >> a >> b;

        if (a == b) {
            cout << "0\n";
            continue;
        }

        if (e[a] > e[b]) {
            cout << "impossible\n";
            continue;
        }

        if (s[b] <= e[a] && e[a] <= e[b]) {
            cout << "1\n";
            continue;
        }

        for (int log = 19; log >= 0; log--) {
            if (s[prevjmp[b][log]] > e[a]) {
                b = prevjmp[b][log];
                ans += (long long) (1 << log);
            }
        }

        b = prevjmp[b][0];

        if (s[b] > e[a]) {
            cout << "impossible\n";
            continue;
        } else {
            cout << ans + 2 << "\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