oj.uz

Submission #573669

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

const int maxn = 100010, SZ = 1000;
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 1315 ms 404216 KB Output is correct
3 Correct 1241 ms 404100 KB Output is correct
4 Correct 927 ms 404484 KB Output is correct
5 Correct 1327 ms 404188 KB Output is correct
6 Correct 1324 ms 404356 KB Output is correct
7 Correct 1284 ms 404368 KB Output is correct
8 Correct 274 ms 209612 KB Output is correct
9 Correct 236 ms 207712 KB Output is correct
10 Correct 627 ms 404956 KB Output is correct
11 Correct 662 ms 404744 KB Output is correct
12 Correct 220 ms 207420 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 6612 KB Output is correct
3 Correct 8 ms 10592 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 5 ms 9556 KB Output is correct
7 Correct 6 ms 10580 KB Output is correct
8 Correct 7 ms 10580 KB Output is correct
9 Correct 5 ms 8608 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 6612 KB Output is correct
3 Correct 8 ms 10592 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 5 ms 9556 KB Output is correct
7 Correct 6 ms 10580 KB Output is correct
8 Correct 7 ms 10580 KB Output is correct
9 Correct 5 ms 8608 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 8 ms 10580 KB Output is correct
13 Correct 7 ms 10496 KB Output is correct
14 Correct 6 ms 10592 KB Output is correct
15 Correct 5 ms 9588 KB Output is correct
16 Correct 6 ms 10580 KB Output is correct
17 Correct 6 ms 10580 KB Output is correct
18 Correct 5 ms 8576 KB Output is correct
19 Correct 375 ms 26980 KB Output is correct
20 Correct 492 ms 26932 KB Output is correct
21 Correct 186 ms 27336 KB Output is correct
22 Correct 46 ms 22272 KB Output is correct
23 Correct 44 ms 27144 KB Output is correct
24 Correct 36 ms 27072 KB Output is correct
25 Correct 262 ms 26772 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 6612 KB Output is correct
3 Correct 8 ms 10592 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 5 ms 9556 KB Output is correct
7 Correct 6 ms 10580 KB Output is correct
8 Correct 7 ms 10580 KB Output is correct
9 Correct 5 ms 8608 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 4 ms 6612 KB Output is correct
12 Correct 10 ms 10580 KB Output is correct
13 Correct 7 ms 10580 KB Output is correct
14 Correct 7 ms 10580 KB Output is correct
15 Correct 5 ms 9556 KB Output is correct
16 Correct 6 ms 10580 KB Output is correct
17 Correct 6 ms 10580 KB Output is correct
18 Correct 5 ms 8532 KB Output is correct
19 Correct 478 ms 403576 KB Output is correct
20 Correct 531 ms 403700 KB Output is correct
21 Correct 252 ms 304204 KB Output is correct
22 Correct 517 ms 403532 KB Output is correct
23 Correct 280 ms 403552 KB Output is correct
24 Correct 323 ms 403548 KB Output is correct
25 Correct 190 ms 206120 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1360 ms 404220 KB Output is correct
2 Correct 1278 ms 404136 KB Output is correct
3 Correct 934 ms 404324 KB Output is correct
4 Correct 262 ms 207552 KB Output is correct
5 Correct 631 ms 404916 KB Output is correct
6 Correct 562 ms 404668 KB Output is correct
7 Correct 617 ms 404744 KB Output is correct
8 Correct 530 ms 404540 KB Output is correct
9 Correct 304 ms 403596 KB Output is correct
10 Execution timed out 1614 ms 403952 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 1315 ms 404216 KB Output is correct
3 Correct 1241 ms 404100 KB Output is correct
4 Correct 927 ms 404484 KB Output is correct
5 Correct 1327 ms 404188 KB Output is correct
6 Correct 1324 ms 404356 KB Output is correct
7 Correct 1284 ms 404368 KB Output is correct
8 Correct 274 ms 209612 KB Output is correct
9 Correct 236 ms 207712 KB Output is correct
10 Correct 627 ms 404956 KB Output is correct
11 Correct 662 ms 404744 KB Output is correct
12 Correct 220 ms 207420 KB Output is correct
13 Correct 4 ms 6612 KB Output is correct
14 Correct 3 ms 6612 KB Output is correct
15 Correct 8 ms 10592 KB Output is correct
16 Correct 7 ms 10580 KB Output is correct
17 Correct 6 ms 10580 KB Output is correct
18 Correct 5 ms 9556 KB Output is correct
19 Correct 6 ms 10580 KB Output is correct
20 Correct 7 ms 10580 KB Output is correct
21 Correct 5 ms 8608 KB Output is correct
22 Correct 3 ms 6612 KB Output is correct
23 Correct 3 ms 6612 KB Output is correct
24 Correct 8 ms 10580 KB Output is correct
25 Correct 7 ms 10496 KB Output is correct
26 Correct 6 ms 10592 KB Output is correct
27 Correct 5 ms 9588 KB Output is correct
28 Correct 6 ms 10580 KB Output is correct
29 Correct 6 ms 10580 KB Output is correct
30 Correct 5 ms 8576 KB Output is correct
31 Correct 375 ms 26980 KB Output is correct
32 Correct 492 ms 26932 KB Output is correct
33 Correct 186 ms 27336 KB Output is correct
34 Correct 46 ms 22272 KB Output is correct
35 Correct 44 ms 27144 KB Output is correct
36 Correct 36 ms 27072 KB Output is correct
37 Correct 262 ms 26772 KB Output is correct
38 Correct 3 ms 6612 KB Output is correct
39 Correct 4 ms 6612 KB Output is correct
40 Correct 10 ms 10580 KB Output is correct
41 Correct 7 ms 10580 KB Output is correct
42 Correct 7 ms 10580 KB Output is correct
43 Correct 5 ms 9556 KB Output is correct
44 Correct 6 ms 10580 KB Output is correct
45 Correct 6 ms 10580 KB Output is correct
46 Correct 5 ms 8532 KB Output is correct
47 Correct 478 ms 403576 KB Output is correct
48 Correct 531 ms 403700 KB Output is correct
49 Correct 252 ms 304204 KB Output is correct
50 Correct 517 ms 403532 KB Output is correct
51 Correct 280 ms 403552 KB Output is correct
52 Correct 323 ms 403548 KB Output is correct
53 Correct 190 ms 206120 KB Output is correct
54 Correct 1360 ms 404220 KB Output is correct
55 Correct 1278 ms 404136 KB Output is correct
56 Correct 934 ms 404324 KB Output is correct
57 Correct 262 ms 207552 KB Output is correct
58 Correct 631 ms 404916 KB Output is correct
59 Correct 562 ms 404668 KB Output is correct
60 Correct 617 ms 404744 KB Output is correct
61 Correct 530 ms 404540 KB Output is correct
62 Correct 304 ms 403596 KB Output is correct
63 Execution timed out 1614 ms 403952 KB Time limit exceeded
64 Halted 0 ms 0 KB -