oj.uz

Submission #573667

# Submission time Handle Problem Language Result Execution time Memory
573667 2022-06-07T04:38:39 Z eecs Event Hopping (BOI22_events) C++17
50 / 100
 1500 ms 326692 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010, SZ = 800;
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); ~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 (a[t][0] <= s && s <= a[t][1]) cout << ans + 1 << "\n";
        else cout << "impossible\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 1183 ms 326000 KB Output is correct
3 Correct 1121 ms 325920 KB Output is correct
4 Correct 819 ms 326144 KB Output is correct
5 Correct 1151 ms 325928 KB Output is correct
6 Correct 1118 ms 325896 KB Output is correct
7 Correct 1123 ms 326092 KB Output is correct
8 Correct 200 ms 169732 KB Output is correct
9 Correct 206 ms 168424 KB Output is correct
10 Correct 518 ms 326648 KB Output is correct
11 Correct 540 ms 326692 KB Output is correct
12 Correct 179 ms 168300 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 3 ms 6596 KB Output is correct
3 Correct 7 ms 9756 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 6 ms 9780 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 3 ms 6596 KB Output is correct
3 Correct 7 ms 9756 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 6 ms 9780 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9044 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 5 ms 8148 KB Output is correct
19 Correct 81 ms 23100 KB Output is correct
20 Correct 205 ms 23100 KB Output is correct
21 Correct 143 ms 23368 KB Output is correct
22 Correct 40 ms 19452 KB Output is correct
23 Correct 37 ms 23228 KB Output is correct
24 Correct 38 ms 23116 KB Output is correct
25 Correct 154 ms 22792 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 3 ms 6596 KB Output is correct
3 Correct 7 ms 9756 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 6 ms 9780 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9044 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 377 ms 325324 KB Output is correct
20 Correct 365 ms 325452 KB Output is correct
21 Correct 220 ms 245476 KB Output is correct
22 Correct 398 ms 325232 KB Output is correct
23 Correct 227 ms 325200 KB Output is correct
24 Correct 266 ms 325236 KB Output is correct
25 Correct 156 ms 166988 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 325980 KB Output is correct
2 Correct 1100 ms 326084 KB Output is correct
3 Correct 810 ms 326012 KB Output is correct
4 Correct 203 ms 168520 KB Output is correct
5 Correct 507 ms 326592 KB Output is correct
6 Correct 503 ms 326424 KB Output is correct
7 Correct 544 ms 326580 KB Output is correct
8 Correct 409 ms 326372 KB Output is correct
9 Correct 248 ms 325220 KB Output is correct
10 Execution timed out 1604 ms 325604 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 Correct 1183 ms 326000 KB Output is correct
3 Correct 1121 ms 325920 KB Output is correct
4 Correct 819 ms 326144 KB Output is correct
5 Correct 1151 ms 325928 KB Output is correct
6 Correct 1118 ms 325896 KB Output is correct
7 Correct 1123 ms 326092 KB Output is correct
8 Correct 200 ms 169732 KB Output is correct
9 Correct 206 ms 168424 KB Output is correct
10 Correct 518 ms 326648 KB Output is correct
11 Correct 540 ms 326692 KB Output is correct
12 Correct 179 ms 168300 KB Output is correct
13 Correct 4 ms 6612 KB Output is correct
14 Correct 3 ms 6596 KB Output is correct
15 Correct 7 ms 9756 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 7 ms 9812 KB Output is correct
18 Correct 5 ms 9044 KB Output is correct
19 Correct 5 ms 9812 KB Output is correct
20 Correct 6 ms 9780 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 3 ms 6612 KB Output is correct
23 Correct 3 ms 6612 KB Output is correct
24 Correct 6 ms 9812 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 6 ms 9812 KB Output is correct
27 Correct 5 ms 9044 KB Output is correct
28 Correct 5 ms 9812 KB Output is correct
29 Correct 6 ms 9812 KB Output is correct
30 Correct 5 ms 8148 KB Output is correct
31 Correct 81 ms 23100 KB Output is correct
32 Correct 205 ms 23100 KB Output is correct
33 Correct 143 ms 23368 KB Output is correct
34 Correct 40 ms 19452 KB Output is correct
35 Correct 37 ms 23228 KB Output is correct
36 Correct 38 ms 23116 KB Output is correct
37 Correct 154 ms 22792 KB Output is correct
38 Correct 3 ms 6612 KB Output is correct
39 Correct 3 ms 6612 KB Output is correct
40 Correct 6 ms 9812 KB Output is correct
41 Correct 6 ms 9812 KB Output is correct
42 Correct 6 ms 9812 KB Output is correct
43 Correct 5 ms 9044 KB Output is correct
44 Correct 5 ms 9812 KB Output is correct
45 Correct 6 ms 9812 KB Output is correct
46 Correct 4 ms 8148 KB Output is correct
47 Correct 377 ms 325324 KB Output is correct
48 Correct 365 ms 325452 KB Output is correct
49 Correct 220 ms 245476 KB Output is correct
50 Correct 398 ms 325232 KB Output is correct
51 Correct 227 ms 325200 KB Output is correct
52 Correct 266 ms 325236 KB Output is correct
53 Correct 156 ms 166988 KB Output is correct
54 Correct 1173 ms 325980 KB Output is correct
55 Correct 1100 ms 326084 KB Output is correct
56 Correct 810 ms 326012 KB Output is correct
57 Correct 203 ms 168520 KB Output is correct
58 Correct 507 ms 326592 KB Output is correct
59 Correct 503 ms 326424 KB Output is correct
60 Correct 544 ms 326580 KB Output is correct
61 Correct 409 ms 326372 KB Output is correct
62 Correct 248 ms 325220 KB Output is correct
63 Execution timed out 1604 ms 325604 KB Time limit exceeded
64 Halted 0 ms 0 KB -