Submission #573631

#	Time	Username	Problem	Language	Result	Execution time	Memory
573631		eecs	Event Hopping (BOI22_events)	C++17	0 / 100	1067 ms	79000 KiB

events

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

const int maxn = 100010, SZ = 300;
int n, q, b[maxn], rmq[20][maxn];
int bel[maxn], bl[maxn], br[maxn];
array<int, 2> a[maxn];
vector<int> tr[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    vector<int> V;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1], V.push_back(a[i][1]);
    }
    sort(V.begin(), V.end());
    V.resize(unique(V.begin(), V.end()) - V.begin());
    fill(b + 1, b + n + 1, n + 1);
    for (int i = 1; i <= n; i++) {
        a[i][0] = lower_bound(V.begin(), V.end(), a[i][0]) - V.begin() + 1;
        a[i][1] = lower_bound(V.begin(), V.end(), a[i][1]) - V.begin() + 1;
        b[a[i][1]] = min(b[a[i][1]], a[i][0]);
    }
    for (int i = 1; i <= n; i++) {
        br[bel[i] = (i - 1) / SZ + 1] = i;
        if (!bl[bel[i]]) bl[bel[i]] = i;
    }
    copy(b + 1, b + n + 1, rmq[0] + 1);
    for (int k = 1; k < 20; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
        }
    }
    auto qmin = [&](int l, int r) {
        int k = __lg(r - l + 1);
        return min(rmq[k][l], rmq[k][r - (1 << k) + 1]);
    };
    auto go = [&](int s, int r) {
        int lb = s + 1, rb = r, ans = 0;
        while (lb <= rb) {
            int mid = (lb + rb) / 2;
            qmin(mid, r) <= s ? lb = (ans = mid) + 1 : rb = mid - 1;
        }
        return ans;
    };
    for (int i = 1; i <= n; i++) {
        for (int j = i; j && j <= br[i]; j = go(j, br[i])) {
            tr[i].push_back(j);
        }
    }
    while (q--) {
        int s, t, ans = 0;
        cin >> s >> t;
        if (s == t) { cout << "0\n"; continue; }
        s = a[s][1];
        for (s = a[s][1]; s && s < a[t][0]; ans++) {
            if (bel[s] + 1 >= bel[a[t][0]]) {
                s = go(s, a[t][1]);
            } else {
                int nxt = qmin(bl[bel[s] + 1], a[t][1]);
                auto it = lower_bound(tr[s].begin(), tr[s].end(), nxt);
                if (it == tr[s].end()) { s = 0; break; }
                ans += it - tr[s].begin() - 1, s = *it;
            }
        }
        if (a[t][0] <= s && s <= a[t][1]) cout << ans + 1 << "\n";
        else cout << "impossible\n";
    }
    return 0;
}

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