Submission #573658

#	Time	Username	Problem	Language	Result	Execution time	Memory
573658		eecs	Event Hopping (BOI22_events)	C++17	40 / 100	1597 ms	248912 KiB

events

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

const int maxn = 100010, SZ = 600;
int n, q, b[maxn], rmq[17][maxn], bel[maxn], bl[maxn], br[maxn];
int num[maxn / SZ + 5][SZ + 5], tmp[maxn];
short pos[maxn][SZ + 5];
array<int, 2> a[maxn];
vector<int> tr[maxn];

int main() {
    // freopen("1_1.in", "r", stdin);
    // freopen("output.txt", "w", stdout);
    double start = clock();
    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 < 17; k++) {
        memcpy(rmq[k], rmq[k - 1], sizeof(rmq[k]));
        for (int i = (1 << (k - 1)) + 1; i <= n; i++) {
            rmq[k][i] = min(rmq[k][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 + (1 << k) - 1], rmq[k][r]);
    };
    auto go = [&](int s, int r) {
        for (int i = __lg(r); ~i && r > s; i--) {
            if (rmq[i][r] > s) r -= 1 << i;
        }
        return r <= s ? 0 : r;
    };
    for (int k = 1; k <= bel[n]; k++) {
        for (int i = br[k], j = br[k]; i >= bl[k]; i--) {
            for (; j >= max(bl[k], b[i]); j--) num[k][j - bl[k]] = j < i ? i : 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        int k = bel[i], L = bl[k], R = br[k];
        tr[i].reserve(R - i);
        for (int j = num[k][i - L]; j && j <= R; j = num[k][j - L]) {
            tr[i].push_back(j);
        }
        for (int j = L, k = 0; j <= R; j++) {
            while (k < tr[i].size() && tr[i][k] < j) k++;
            pos[i][j - L] = k;
        }
    }
    cerr << clock() - start << endl;
    while (q--) {
        int s, t, ans = 0;
        cin >> s >> t;
        if (s == t) { cout << "0\n"; continue; }
        for (s = a[s][1]; s && s < a[t][0]; ans++) {
            if (bel[s] == bel[a[t][0]]) {
                for (int i = a[t][0], j = a[t][0]; i >= s; i--) {
                    int v = i == a[t][0] ? qmin(i, a[t][1]) : b[i];
                    for (; j >= max(s, v); j--) tmp[j - s] = j < i ? i : 0;
                }
                for (int o = s; s && s < a[t][0]; ans++) {
                    s = tmp[s - o];
                }
                break;
            }
            int nxt = qmin(bl[bel[s] + 1], a[t][1]);
            if (nxt <= s) {
                s = go(s, a[t][1]);
            } else {
                if (tr[s].empty() || nxt > tr[s].back()) { s = 0; break; }
                int i = pos[s][nxt - bl[bel[s]]];
                ans += i, s = tr[s][i];
            }
        }
        if (a[t][0] <= s && s <= a[t][1]) cout << ans + 1 << "\n";
        else cout << "impossible\n";
    }
    cerr << clock() - start << endl;
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             while (k < tr[i].size() && tr[i][k] < j) k++;
      |                    ~~^~~~~~~~~~~~~~

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