oj.uz

Submission #917152

# Submission time Handle Problem Language Result Execution time Memory
917152 2024-01-27T10:24:00 Z 406 Event Hopping (BOI22_events) C++17
0 / 100
 137 ms 159432 KB 
#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;

const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;
const int LG = 20;

namespace RMQ {
        ar mn[LG][N];

        void build(ar a[], int n) {
                FOR(i, 0, n) mn[0][i] = a[i];

                FOR(l, 0, LG - 1) FOR(i, 0, n)
                        mn[l + 1][i] = min(mn[l][i], mn[l][i + (1 << l)]);
        }

        int get(int l, int r) { //[l, r)
                int t = __lg(r - l);
                return min(mn[t][l], mn[t][r - (1 << t)])[1];
        }
}

int pr[N][LG], h[N], D[2 * N], loc[N], n, q;
ar3 it[N];
ar en[2 * N];

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> q;
        FOR(i, 0, n) {
                cin >> it[i][0] >> it[i][1];
                it[i][2] = i;
                D[i << 1] = it[i][0];
                D[i << 1 | 1] = it[i][1];
        }
        fill(en, en + 2 * n, ar{INF, INF});
        sort(D, D + 2 * n);
        sort(it, it + n, [](const auto &A, const auto &B) {
                if (A[0] != B[0]) return A[0] < B[0];
                return A[2] < B[2];
        });


        FOR(i, 0, n) {
                it[i][0] = lower_bound(D, D + 2 * n, it[i][0]) - D;
                it[i][1] = lower_bound(D, D + 2 * n, it[i][1]) - D;
                en[it[i][1]] = min(en[it[i][1]], ar{it[i][0], i});
                loc[it[i][2]] = i;
        }
        RMQ::build(en, 2 * n);

        FOR(i, 0, n) {
                pr[i][0] = i;
                auto [l, r, x] = it[i];
                int idx = RMQ::get(l, r + 1);
                assert(idx <= i);
                if (idx != i) {
                        h[i] = h[idx] + 1;
                        pr[i][0] = idx;
                        FOR(l, 0, LG - 1)
                                pr[i][l + 1] = pr[pr[i][l]][l];
                }
        }

        while (q--) {
                int s, e;
                cin >> s >> e;
                --s, --e;
                s = loc[s], e = loc[e];
                if (it[e][1] < it[s][0] || it[s][1] > it[e][1]) cout << "impossible\n";
                else if (s == e) cout << 0 << '\n';
                else if (it[s][1] < it[e][0]) {
                        int sr = it[s][1], v = e;

                        for (int i = LG - 1; i >= 0; --i) {
                                int l = it[pr[v][i]][0];
                                if (l > sr)
                                        v = pr[v][i];
                        }
                        v = pr[v][0];
                        if (it[v][0] > sr) cout << "impossible\n";
                        else cout << h[e] - h[v] + 1 << '\n';
                }
        }

        return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49500 KB Output is correct
2 Runtime error 129 ms 159432 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49500 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Incorrect 8 ms 49756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49500 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Incorrect 8 ms 49756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49500 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Incorrect 8 ms 49756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 159428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49500 KB Output is correct
2 Runtime error 129 ms 159432 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -