oj.uz

답안 #573665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573665 2022-06-07T04:35:08 Z eecs Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 403548 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];
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) {
        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];
        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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Execution timed out 1596 ms 403544 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 8 ms 10588 KB Output is correct
4 Correct 8 ms 10496 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 6 ms 9620 KB Output is correct
7 Correct 8 ms 10580 KB Output is correct
8 Correct 7 ms 10580 KB Output is correct
9 Correct 5 ms 8532 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 8 ms 10588 KB Output is correct
4 Correct 8 ms 10496 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 6 ms 9620 KB Output is correct
7 Correct 8 ms 10580 KB Output is correct
8 Correct 7 ms 10580 KB Output is correct
9 Correct 5 ms 8532 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 10580 KB Output is correct
13 Correct 6 ms 10580 KB Output is correct
14 Correct 8 ms 10580 KB Output is correct
15 Correct 8 ms 9556 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 8532 KB Output is correct
19 Correct 387 ms 26892 KB Output is correct
20 Correct 525 ms 26956 KB Output is correct
21 Correct 177 ms 27180 KB Output is correct
22 Correct 50 ms 22288 KB Output is correct
23 Correct 44 ms 27020 KB Output is correct
24 Correct 51 ms 26996 KB Output is correct
25 Correct 281 ms 26720 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 8 ms 10588 KB Output is correct
4 Correct 8 ms 10496 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 6 ms 9620 KB Output is correct
7 Correct 8 ms 10580 KB Output is correct
8 Correct 7 ms 10580 KB Output is correct
9 Correct 5 ms 8532 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 10580 KB Output is correct
14 Correct 6 ms 10580 KB Output is correct
15 Correct 7 ms 9556 KB Output is correct
16 Correct 6 ms 10580 KB Output is correct
17 Correct 6 ms 10476 KB Output is correct
18 Correct 6 ms 8548 KB Output is correct
19 Correct 471 ms 403184 KB Output is correct
20 Correct 462 ms 403280 KB Output is correct
21 Correct 256 ms 303752 KB Output is correct
22 Correct 500 ms 403172 KB Output is correct
23 Correct 296 ms 403148 KB Output is correct
24 Correct 294 ms 403188 KB Output is correct
25 Correct 202 ms 205704 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1612 ms 403548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Execution timed out 1596 ms 403544 KB Time limit exceeded
3 Halted 0 ms 0 KB -