oj.uz

Submission #634371

# Submission time Handle Problem Language Result Execution time Memory
634371 2022-08-24T10:09:01 Z dooompy Event Hopping (BOI22_events) C++17
0 / 100
 383 ms 13604 KB 
#include <bits/stdc++.h>

using namespace std;

int s[100005], e[100005];

vector<int> comp;

pair<int, int> tree[4 * 100005];

void update(int x, int l, int r, int loc, pair<int, int> stuff) {
    if (l == r) {
        tree[x] = min(tree[x], stuff);
        return;
    }

    int mid = (l + r) / 2;

    if (loc <= mid) update(2 * x, l, mid, loc, stuff);
    else update(2 * x + 1, mid + 1, r, loc, stuff);

    tree[x] = min(tree[2 * x], tree[2 * x + 1]);
}

int convert(int x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
}

int prevjmp[100005][20];

pair<int, int> get(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[x];
    if (l > qr || r < ql) return {1e9, 1e9};

    int mid = (l + r) / 2;

    return min(get(2 * x, l, mid, ql, qr), get(2 * x + 1, mid + 1, r, ql, qr));
}

int main() {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> e[i];
        comp.push_back(s[i]);
        comp.push_back(e[i]);
    }

    fill(&tree[0], &tree[0] + sizeof(tree) / sizeof(tree[0]), make_pair(1e9, 1e9));

    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

    int sz = comp.size();

    for (int i = 1; i <= n; i++) {
        // find furtherst cano back
        s[i] = convert(s[i]);
        e[i] = convert(e[i]);

        update(1, 1, sz, e[i], {s[i], i});
    }

    for (int i = 1; i <= n; i++) {
        prevjmp[i][0] = get(1, 1, sz, s[i], e[i]).second;
    }

    for (int log = 1; log < 20; log++) {
        for (int i = 1; i <= n; i++) {
            prevjmp[i][log] = prevjmp[prevjmp[i][log-1]][log-1];
        }
    }


    for (int i = 0; i < q; i++) {
        long long ans = 0;
        int a, b; cin >> a >> b;

        if (a == b) {
            cout << "0\n";
            continue;
        }

        if (e[a] > e[b]) {
            cout << "impossible\n";
            continue;
        }

        if (s[b] <= e[a] && e[a] <= e[b]) {
            cout << "1\n";
            continue;
        }

        for (int log = 19; log >= 0; log--) {
            if (e[prevjmp[b][log]] > e[a]) {
                b = prevjmp[b][log];
                ans += (long long) (1 << log);
            }
        }

        b = prevjmp[b][0];

        if (e[b] > e[a]) {
            cout << "impossible\n";
            continue;
        } else {
            cout << ans + 2 << "\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 383 ms 13604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -