oj.uz

Submission #573663

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

const int maxn = 100010, SZ = 750;
int n, q, b[maxn], rmq[17][maxn], bel[maxn], bl[maxn], br[maxn];
int num[maxn / SZ + 5][SZ + 5], tmp[SZ + 5];
short pos[maxn][SZ + 5];
array<int, 2> a[maxn];
vector<int> tr[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) {
        if (b[s + 1] <= s && (r == s + 1 || qmin(s + 2, r) > s)) return s + 1;
        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;
        }
    }
    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";
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 1070 ms 307780 KB Output is correct
3 Correct 1006 ms 307676 KB Output is correct
4 Correct 908 ms 307720 KB Output is correct
5 Execution timed out 1549 ms 307720 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8916 KB Output is correct
2 Correct 5 ms 8984 KB Output is correct
3 Correct 9 ms 11636 KB Output is correct
4 Correct 9 ms 11628 KB Output is correct
5 Correct 8 ms 11652 KB Output is correct
6 Correct 6 ms 11604 KB Output is correct
7 Correct 7 ms 11604 KB Output is correct
8 Correct 6 ms 11604 KB Output is correct
9 Correct 6 ms 11632 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8916 KB Output is correct
2 Correct 5 ms 8984 KB Output is correct
3 Correct 9 ms 11636 KB Output is correct
4 Correct 9 ms 11628 KB Output is correct
5 Correct 8 ms 11652 KB Output is correct
6 Correct 6 ms 11604 KB Output is correct
7 Correct 7 ms 11604 KB Output is correct
8 Correct 6 ms 11604 KB Output is correct
9 Correct 6 ms 11632 KB Output is correct
10 Correct 4 ms 8916 KB Output is correct
11 Correct 4 ms 8916 KB Output is correct
12 Correct 8 ms 11680 KB Output is correct
13 Correct 9 ms 11600 KB Output is correct
14 Correct 8 ms 11604 KB Output is correct
15 Correct 6 ms 11592 KB Output is correct
16 Correct 6 ms 11616 KB Output is correct
17 Correct 7 ms 11604 KB Output is correct
18 Correct 7 ms 11604 KB Output is correct
19 Correct 146 ms 24144 KB Output is correct
20 Correct 278 ms 24140 KB Output is correct
21 Correct 160 ms 24396 KB Output is correct
22 Correct 40 ms 24468 KB Output is correct
23 Correct 37 ms 24192 KB Output is correct
24 Correct 38 ms 24200 KB Output is correct
25 Correct 159 ms 23964 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8916 KB Output is correct
2 Correct 5 ms 8984 KB Output is correct
3 Correct 9 ms 11636 KB Output is correct
4 Correct 9 ms 11628 KB Output is correct
5 Correct 8 ms 11652 KB Output is correct
6 Correct 6 ms 11604 KB Output is correct
7 Correct 7 ms 11604 KB Output is correct
8 Correct 6 ms 11604 KB Output is correct
9 Correct 6 ms 11632 KB Output is correct
10 Correct 4 ms 8944 KB Output is correct
11 Correct 6 ms 8940 KB Output is correct
12 Correct 8 ms 11604 KB Output is correct
13 Correct 7 ms 11708 KB Output is correct
14 Correct 8 ms 11604 KB Output is correct
15 Correct 6 ms 11604 KB Output is correct
16 Correct 6 ms 11668 KB Output is correct
17 Correct 6 ms 11604 KB Output is correct
18 Correct 7 ms 11604 KB Output is correct
19 Correct 462 ms 307088 KB Output is correct
20 Correct 443 ms 307044 KB Output is correct
21 Correct 222 ms 306856 KB Output is correct
22 Correct 431 ms 307144 KB Output is correct
23 Correct 218 ms 307144 KB Output is correct
24 Correct 236 ms 307084 KB Output is correct
25 Correct 191 ms 306716 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 307804 KB Output is correct
2 Correct 1051 ms 307756 KB Output is correct
3 Correct 916 ms 307664 KB Output is correct
4 Correct 241 ms 308164 KB Output is correct
5 Correct 589 ms 308048 KB Output is correct
6 Correct 960 ms 307900 KB Output is correct
7 Correct 1058 ms 307852 KB Output is correct
8 Correct 644 ms 307928 KB Output is correct
9 Correct 229 ms 307088 KB Output is correct
10 Execution timed out 1614 ms 307424 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 1070 ms 307780 KB Output is correct
3 Correct 1006 ms 307676 KB Output is correct
4 Correct 908 ms 307720 KB Output is correct
5 Execution timed out 1549 ms 307720 KB Time limit exceeded
6 Halted 0 ms 0 KB -