oj.uz

Submission #573677

# Submission time Handle Problem Language Result Execution time Memory
573677 2022-06-07T04:55:46 Z eecs Event Hopping (BOI22_events) C++17
50 / 100
 1500 ms 326756 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 - 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 1252 ms 325896 KB Output is correct
3 Correct 1138 ms 325864 KB Output is correct
4 Correct 820 ms 326112 KB Output is correct
5 Correct 1153 ms 325936 KB Output is correct
6 Correct 1149 ms 326004 KB Output is correct
7 Correct 1162 ms 326008 KB Output is correct
8 Correct 182 ms 169676 KB Output is correct
9 Correct 179 ms 168424 KB Output is correct
10 Correct 540 ms 326756 KB Output is correct
11 Correct 586 ms 326640 KB Output is correct
12 Correct 166 ms 168264 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 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 5 ms 9812 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 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 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 5 ms 9812 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 6572 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 5 ms 9044 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 87 ms 23052 KB Output is correct
20 Correct 200 ms 23084 KB Output is correct
21 Correct 145 ms 23312 KB Output is correct
22 Correct 42 ms 19436 KB Output is correct
23 Correct 41 ms 23208 KB Output is correct
24 Correct 34 ms 23172 KB Output is correct
25 Correct 151 ms 22816 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 3 ms 6612 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 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 5 ms 9812 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 7 ms 9812 KB Output is correct
13 Correct 6 ms 9768 KB Output is correct
14 Correct 7 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 5 ms 9812 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 404 ms 325304 KB Output is correct
20 Correct 403 ms 325492 KB Output is correct
21 Correct 210 ms 245432 KB Output is correct
22 Correct 447 ms 325304 KB Output is correct
23 Correct 244 ms 325228 KB Output is correct
24 Correct 293 ms 325300 KB Output is correct
25 Correct 140 ms 166988 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 325912 KB Output is correct
2 Correct 1105 ms 325868 KB Output is correct
3 Correct 824 ms 326088 KB Output is correct
4 Correct 179 ms 168396 KB Output is correct
5 Correct 548 ms 326624 KB Output is correct
6 Correct 562 ms 326424 KB Output is correct
7 Correct 569 ms 326336 KB Output is correct
8 Correct 459 ms 326380 KB Output is correct
9 Correct 244 ms 325320 KB Output is correct
10 Execution timed out 1589 ms 325664 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 1252 ms 325896 KB Output is correct
3 Correct 1138 ms 325864 KB Output is correct
4 Correct 820 ms 326112 KB Output is correct
5 Correct 1153 ms 325936 KB Output is correct
6 Correct 1149 ms 326004 KB Output is correct
7 Correct 1162 ms 326008 KB Output is correct
8 Correct 182 ms 169676 KB Output is correct
9 Correct 179 ms 168424 KB Output is correct
10 Correct 540 ms 326756 KB Output is correct
11 Correct 586 ms 326640 KB Output is correct
12 Correct 166 ms 168264 KB Output is correct
13 Correct 3 ms 6612 KB Output is correct
14 Correct 3 ms 6612 KB Output is correct
15 Correct 7 ms 9812 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 6 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 5 ms 9812 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 6572 KB Output is correct
24 Correct 7 ms 9812 KB Output is correct
25 Correct 7 ms 9812 KB Output is correct
26 Correct 7 ms 9812 KB Output is correct
27 Correct 5 ms 9044 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Correct 5 ms 9812 KB Output is correct
30 Correct 4 ms 8148 KB Output is correct
31 Correct 87 ms 23052 KB Output is correct
32 Correct 200 ms 23084 KB Output is correct
33 Correct 145 ms 23312 KB Output is correct
34 Correct 42 ms 19436 KB Output is correct
35 Correct 41 ms 23208 KB Output is correct
36 Correct 34 ms 23172 KB Output is correct
37 Correct 151 ms 22816 KB Output is correct
38 Correct 3 ms 6612 KB Output is correct
39 Correct 3 ms 6612 KB Output is correct
40 Correct 7 ms 9812 KB Output is correct
41 Correct 6 ms 9768 KB Output is correct
42 Correct 7 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 5 ms 9812 KB Output is correct
46 Correct 4 ms 8148 KB Output is correct
47 Correct 404 ms 325304 KB Output is correct
48 Correct 403 ms 325492 KB Output is correct
49 Correct 210 ms 245432 KB Output is correct
50 Correct 447 ms 325304 KB Output is correct
51 Correct 244 ms 325228 KB Output is correct
52 Correct 293 ms 325300 KB Output is correct
53 Correct 140 ms 166988 KB Output is correct
54 Correct 1182 ms 325912 KB Output is correct
55 Correct 1105 ms 325868 KB Output is correct
56 Correct 824 ms 326088 KB Output is correct
57 Correct 179 ms 168396 KB Output is correct
58 Correct 548 ms 326624 KB Output is correct
59 Correct 562 ms 326424 KB Output is correct
60 Correct 569 ms 326336 KB Output is correct
61 Correct 459 ms 326380 KB Output is correct
62 Correct 244 ms 325320 KB Output is correct
63 Execution timed out 1589 ms 325664 KB Time limit exceeded
64 Halted 0 ms 0 KB -