oj.uz

답안 #573661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573661 2022-06-07T04:20:29 Z eecs Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 210580 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010, SZ = 500;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 1233 ms 210120 KB Output is correct
3 Correct 1151 ms 210136 KB Output is correct
4 Correct 808 ms 210012 KB Output is correct
5 Execution timed out 1608 ms 210036 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 8988 KB Output is correct
3 Correct 9 ms 10964 KB Output is correct
4 Correct 7 ms 10964 KB Output is correct
5 Correct 7 ms 10964 KB Output is correct
6 Correct 6 ms 10976 KB Output is correct
7 Correct 6 ms 10868 KB Output is correct
8 Correct 6 ms 10944 KB Output is correct
9 Correct 7 ms 10964 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 8988 KB Output is correct
3 Correct 9 ms 10964 KB Output is correct
4 Correct 7 ms 10964 KB Output is correct
5 Correct 7 ms 10964 KB Output is correct
6 Correct 6 ms 10976 KB Output is correct
7 Correct 6 ms 10868 KB Output is correct
8 Correct 6 ms 10944 KB Output is correct
9 Correct 7 ms 10964 KB Output is correct
10 Correct 4 ms 8916 KB Output is correct
11 Correct 4 ms 8916 KB Output is correct
12 Correct 9 ms 10964 KB Output is correct
13 Correct 9 ms 10964 KB Output is correct
14 Correct 7 ms 10964 KB Output is correct
15 Correct 6 ms 10964 KB Output is correct
16 Correct 8 ms 10964 KB Output is correct
17 Correct 7 ms 10896 KB Output is correct
18 Correct 6 ms 10876 KB Output is correct
19 Correct 144 ms 19480 KB Output is correct
20 Correct 279 ms 19608 KB Output is correct
21 Correct 125 ms 19676 KB Output is correct
22 Correct 37 ms 19788 KB Output is correct
23 Correct 33 ms 19628 KB Output is correct
24 Correct 37 ms 19532 KB Output is correct
25 Correct 177 ms 19400 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 8988 KB Output is correct
3 Correct 9 ms 10964 KB Output is correct
4 Correct 7 ms 10964 KB Output is correct
5 Correct 7 ms 10964 KB Output is correct
6 Correct 6 ms 10976 KB Output is correct
7 Correct 6 ms 10868 KB Output is correct
8 Correct 6 ms 10944 KB Output is correct
9 Correct 7 ms 10964 KB Output is correct
10 Correct 6 ms 8916 KB Output is correct
11 Correct 5 ms 8868 KB Output is correct
12 Correct 7 ms 10964 KB Output is correct
13 Correct 9 ms 10964 KB Output is correct
14 Correct 7 ms 10944 KB Output is correct
15 Correct 6 ms 10964 KB Output is correct
16 Correct 6 ms 10964 KB Output is correct
17 Correct 7 ms 10964 KB Output is correct
18 Correct 7 ms 10964 KB Output is correct
19 Correct 347 ms 209524 KB Output is correct
20 Correct 302 ms 209420 KB Output is correct
21 Correct 169 ms 209296 KB Output is correct
22 Correct 303 ms 209444 KB Output is correct
23 Correct 159 ms 209468 KB Output is correct
24 Correct 173 ms 209508 KB Output is correct
25 Correct 149 ms 209024 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1247 ms 210104 KB Output is correct
2 Correct 1144 ms 210044 KB Output is correct
3 Correct 802 ms 210172 KB Output is correct
4 Correct 201 ms 210580 KB Output is correct
5 Correct 456 ms 210460 KB Output is correct
6 Correct 1214 ms 210300 KB Output is correct
7 Correct 1327 ms 210420 KB Output is correct
8 Correct 661 ms 210488 KB Output is correct
9 Correct 157 ms 209512 KB Output is correct
10 Execution timed out 1600 ms 210028 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 1233 ms 210120 KB Output is correct
3 Correct 1151 ms 210136 KB Output is correct
4 Correct 808 ms 210012 KB Output is correct
5 Execution timed out 1608 ms 210036 KB Time limit exceeded
6 Halted 0 ms 0 KB -