Submission #644814

#	Time	Username	Problem	Language	Result	Execution time	Memory
644814		FedShat	Event Hopping (BOI22_events)	C++17	40 / 100	1583 ms	10612 KiB

events

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct SegTree {
    vector<pair<int, int>> tree;
    int n;

    SegTree(int n) : n(n) {
        tree.resize(4 * n, {INF, -1});
    }

    void update(int v, int l, int r, int i, pair<int, int> x) {
        if (l + 1 == r) {
            tree[v] = min(tree[v], x);
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            update(2 * v + 1, l, m, i, x);
        } else {
            update(2 * v + 2, m, r, i, x);
        }
        tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update(int i, pair<int, int> x) {
        update(0, 0, n, i, x);
    }

    pair<int, int> get(int v, int l, int r, int li, int ri) {
        if (li >= r || l >= ri) {
            return {INF, -1};
        }
        if (li <= l && r <= ri) {
            return tree[v];
        }
        int m = (l + r) / 2;
        return min(get(2 * v + 1, l, m, li, ri), get(2 * v + 2, m, r, li, ri));
    }

    int get(int li, int ri) {
        return get(0, 0, n, li, ri).second;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, q;
    cin >> n >> q;
    vector<array<int, 3>> lr(n);
    vector<int> coords;
    for (int i = 0; i < n; ++i) {
        cin >> lr[i][0] >> lr[i][1];
        lr[i][2] = i;
        coords.push_back(lr[i][0]);
        coords.push_back(lr[i][1]);
    }
    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
    sort(lr.begin(), lr.end());
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        p[lr[i][2]] = i;
    }
    for (int i = 0; i < n; ++i) {
        auto &[l, r, ii] = lr[i];
        l = lower_bound(coords.begin(), coords.end(), l) - coords.begin();
        r = lower_bound(coords.begin(), coords.end(), r) - coords.begin();
    }
    SegTree t(coords.size());
    auto can = [&](int i, int j) {// i -> j
        auto [li, ri, ii] = lr[i];
        auto [lj, rj, jj] = lr[j];
        return lj <= ri && ri <= rj;
    };
    vector<int> prv(n);
    for (int i = 0; i < n; ++i) {
        // int ind = -1;
        // for (int j = 0; j < i; ++j) {
        //     if (can(j, i)) {
        //         ind = j;
        //         break;
        //     }
        // }
        // prv[i] = ind;
        auto [l, r, _] = lr[i];
        prv[i] = t.get(l, r + 1);
        t.update(r, {l, i});
    }
    constexpr int k = 2;
    vector<vector<int>> up(k, vector<int>(n, -1));
    up[0] = prv;
    for (int i = 1; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            if (up[i - 1][j] != -1) {
                up[i][j] = up[i - 1][up[i - 1][j]];
            }
        }
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        a = p[a];
        b = p[b];
        int ans = 0;
        for (int i = k - 1; i >= 0; --i) {
            if (up[i][b] != -1 && !can(a, up[i][b]) && lr[up[i][b]][0] > lr[a][1]) {
                b = up[i][b];
                ans += (1 << i);
            }
        }
        if (!can(a, b)) {
            b = up[0][b];
            ++ans;
        }
        while (!can(a, b)) {
            if (prv[b] == -1) {
                ans = -1;
                break;
            }
            b = prv[b];
            ++ans;
        }
        if (b == -1 || !can(a, b)) {
            ans = -1;
        } else if (a != b) {
            ++ans;
        }
        if (ans == -1) {
            cout << "impossible\n";
        } else {
            cout << ans << "\n";
        }
    }
}

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