Submission #917163

#	Time	Username	Problem	Language	Result	Execution time	Memory
917163		406	Event Hopping (BOI22_events)	C++17	100 / 100	161 ms	90816 KiB

events

#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;

const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;
const int LG = 20;

namespace RMQ {
        ar mn[LG][N];

        void build(ar a[], int n) {
                FOR(i, 0, n) mn[0][i] = a[i];

                FOR(l, 0, LG - 1) for (int i = 0; i + (2 << l) <= n; ++i)
                        mn[l + 1][i] = min(mn[l][i], mn[l][i + (1 << l)]);
        }

        int get(int l, int r) { //[l, r)
                int t = __lg(r - l);
                return min(mn[t][l], mn[t][r - (1 << t)])[1];
        }
}

int pr[N][LG], h[N], D[2 * N], loc[N], n, q;
ar3 it[N];
ar en[2 * N];

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> q;
        FOR(i, 0, n) {
                cin >> it[i][0] >> it[i][1];
                it[i][2] = i;
                D[i << 1] = it[i][0];
                D[i << 1 | 1] = it[i][1];
        }
        fill(en, en + 2 * n, ar{INF, INF});
        sort(D, D + 2 * n);
        sort(it, it + n, [](const auto &A, const auto &B) {
                if (A[0] != B[0]) return A[0] < B[0];
                return A[2] < B[2];
        });


        FOR(i, 0, n) {
                it[i][0] = lower_bound(D, D + 2 * n, it[i][0]) - D;
                it[i][1] = lower_bound(D, D + 2 * n, it[i][1]) - D;
                en[it[i][1]] = min(en[it[i][1]], ar{it[i][0], i});
                loc[it[i][2]] = i;
        }
        RMQ::build(en, 2 * n);

        FOR(i, 0, n) {
                pr[i][0] = i;
                auto [l, r, x] = it[i];
                int idx = RMQ::get(l, r + 1);
                if (idx != i) {
                        h[i] = h[idx] + 1;
                        pr[i][0] = idx;
                        FOR(l, 0, LG - 1)
                                pr[i][l + 1] = pr[pr[i][l]][l];
                }
        }

        while (q--) {
                int s, e;
                cin >> s >> e;
                --s, --e;
                s = loc[s], e = loc[e];
                if (it[e][1] < it[s][0] || it[s][1] > it[e][1]) cout << "impossible\n";
                else if (s == e) cout << 0 << '\n';
                else if (it[s][1] < it[e][0]) {
                        int sr = it[s][1], v = e;

                        for (int i = LG - 1; i >= 0; --i) {
                                int l = it[pr[v][i]][0];
                                if (l > sr)
                                        v = pr[v][i];
                        }
                        v = pr[v][0];
                        if (it[v][0] > sr) cout << "impossible\n";
                        else cout << h[e] - h[v] + 1 << '\n';
                }
                else cout << "1\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