Submission #573627

#	Time	Username	Problem	Language	Result	Execution time	Memory
573627		eecs	Event Hopping (BOI22_events)	C++17	25 / 100	1598 ms	8968 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], mn[maxn];
array<int, 2> a[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]);
    };
    for (int k = 1; k <= bel[n]; k++) {
        for (int i = bl[k]; i <= br[k]; i++) {
            mn[i] = min(i == bl[k] ? INT_MAX : mn[i - 1], b[i]);
        }
    }
    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;
    };
    auto brute = [&](int &s, int l, int r) {
        int ans = 0;
        while (s < l) {
            s = go(s, r), ans++;
            if (!s) break;
        }
        return ans;
    };
    while (q--) {
        int s, t;
        cin >> s >> t;
        if (s == t) { cout << "0\n"; continue; }
        s = a[s][1];
        int ans = brute(s, a[t][0], a[t][1]);
        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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30