oj.uz

Submission #573680

# Submission time Handle Problem Language Result Execution time Memory
573680 2022-06-07T05:00:43 Z eecs Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 522268 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010, SZ = 1300;
int n, q, b[maxn], rmq[17][maxn], bel[maxn], bl[maxn], br[maxn];
int num[maxn / SZ + 5][SZ + 5], tmp[maxn], sz[maxn], rb[maxn];
short pos[maxn][SZ + 5], tr[maxn][SZ + 5];
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 < 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) {
        r = min(r, rb[s]);
        if (b[r] <= s) return r;
        for (int i = __lg(r - s + 1); ~i && r > s; i--) {
            if (rmq[i][r] > s) r -= 1 << i;
        }
        return r <= s ? 0 : r;
    };
    for (int i = 1; i <= n; i++) {
        rb[i] = n, rb[i] = go(i, n);
    }
    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];
        for (int j = num[k][i - L]; j && j <= R; j = num[k][j - L]) {
            tr[i][sz[i]++] = j - L;
        }
        for (int j = 0, k = 0; j <= R - L; j++) {
            while (k < sz[i] && tr[i][k] < j) k++;
            pos[i][j] = k;
        }
    }
    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 = max(s, i == a[t][0] ? qmin(i, a[t][1]) : b[i]);
                    for (; j >= v; j--) tmp[j] = j < i ? i : 0;
                }
                for (; s && s < a[t][0]; ans++) s = tmp[s];
                break;
            }
            int nxt = qmin(bl[bel[s] + 1], a[t][1]);
            if (nxt <= s) {
                s = go(s, a[t][1]);
            } else {
                if (!sz[s] || nxt - bl[bel[s]] > tr[s][sz[s] - 1]) { s = 0; break; }
                int i = pos[s][nxt - bl[bel[s]]];
                ans += i, s = bl[bel[s]] + tr[s][i];
                if (s < a[t][0]) s = go(s, a[t][1]), ans++;
            }
        }
        if (a[t][0] <= s && s <= a[t][1]) cout << ans + 1 << "\n";
        else cout << "impossible\n";
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Execution timed out 1509 ms 521496 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 9 ms 11748 KB Output is correct
4 Correct 10 ms 11732 KB Output is correct
5 Correct 8 ms 11732 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 7 ms 11772 KB Output is correct
8 Correct 7 ms 11780 KB Output is correct
9 Correct 5 ms 9172 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 9 ms 11748 KB Output is correct
4 Correct 10 ms 11732 KB Output is correct
5 Correct 8 ms 11732 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 7 ms 11772 KB Output is correct
8 Correct 7 ms 11780 KB Output is correct
9 Correct 5 ms 9172 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 9 ms 11732 KB Output is correct
13 Correct 7 ms 11732 KB Output is correct
14 Correct 7 ms 11776 KB Output is correct
15 Correct 5 ms 10452 KB Output is correct
16 Correct 7 ms 11732 KB Output is correct
17 Correct 6 ms 11732 KB Output is correct
18 Correct 5 ms 9172 KB Output is correct
19 Correct 257 ms 32976 KB Output is correct
20 Correct 532 ms 32776 KB Output is correct
21 Correct 236 ms 33112 KB Output is correct
22 Correct 55 ms 26688 KB Output is correct
23 Correct 53 ms 32948 KB Output is correct
24 Correct 45 ms 32992 KB Output is correct
25 Correct 327 ms 32636 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 9 ms 11748 KB Output is correct
4 Correct 10 ms 11732 KB Output is correct
5 Correct 8 ms 11732 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 7 ms 11772 KB Output is correct
8 Correct 7 ms 11780 KB Output is correct
9 Correct 5 ms 9172 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6604 KB Output is correct
12 Correct 9 ms 11720 KB Output is correct
13 Correct 7 ms 11732 KB Output is correct
14 Correct 9 ms 11732 KB Output is correct
15 Correct 7 ms 10492 KB Output is correct
16 Correct 7 ms 11732 KB Output is correct
17 Correct 9 ms 11732 KB Output is correct
18 Correct 5 ms 9172 KB Output is correct
19 Correct 661 ms 520892 KB Output is correct
20 Correct 629 ms 521016 KB Output is correct
21 Correct 343 ms 392548 KB Output is correct
22 Correct 702 ms 520948 KB Output is correct
23 Correct 430 ms 520872 KB Output is correct
24 Correct 475 ms 520936 KB Output is correct
25 Correct 233 ms 264776 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1493 ms 521580 KB Output is correct
2 Correct 1451 ms 521536 KB Output is correct
3 Correct 1169 ms 521692 KB Output is correct
4 Correct 292 ms 266328 KB Output is correct
5 Correct 806 ms 522268 KB Output is correct
6 Correct 700 ms 522028 KB Output is correct
7 Correct 711 ms 521956 KB Output is correct
8 Correct 739 ms 521752 KB Output is correct
9 Correct 395 ms 520868 KB Output is correct
10 Execution timed out 1542 ms 521340 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Execution timed out 1509 ms 521496 KB Time limit exceeded
3 Halted 0 ms 0 KB -