oj.uz

Submission #644814

# Submission time Handle Problem Language Result Execution time Memory
644814 2022-09-25T09:44:47 Z FedShat Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 10612 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct SegTree {
    vector<pair<int, int>> tree;
    int n;

    SegTree(int n) : n(n) {
        tree.resize(4 * n, {INF, -1});
    }

    void update(int v, int l, int r, int i, pair<int, int> x) {
        if (l + 1 == r) {
            tree[v] = min(tree[v], x);
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            update(2 * v + 1, l, m, i, x);
        } else {
            update(2 * v + 2, m, r, i, x);
        }
        tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update(int i, pair<int, int> x) {
        update(0, 0, n, i, x);
    }

    pair<int, int> get(int v, int l, int r, int li, int ri) {
        if (li >= r || l >= ri) {
            return {INF, -1};
        }
        if (li <= l && r <= ri) {
            return tree[v];
        }
        int m = (l + r) / 2;
        return min(get(2 * v + 1, l, m, li, ri), get(2 * v + 2, m, r, li, ri));
    }

    int get(int li, int ri) {
        return get(0, 0, n, li, ri).second;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, q;
    cin >> n >> q;
    vector<array<int, 3>> lr(n);
    vector<int> coords;
    for (int i = 0; i < n; ++i) {
        cin >> lr[i][0] >> lr[i][1];
        lr[i][2] = i;
        coords.push_back(lr[i][0]);
        coords.push_back(lr[i][1]);
    }
    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
    sort(lr.begin(), lr.end());
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        p[lr[i][2]] = i;
    }
    for (int i = 0; i < n; ++i) {
        auto &[l, r, ii] = lr[i];
        l = lower_bound(coords.begin(), coords.end(), l) - coords.begin();
        r = lower_bound(coords.begin(), coords.end(), r) - coords.begin();
    }
    SegTree t(coords.size());
    auto can = [&](int i, int j) {// i -> j
        auto [li, ri, ii] = lr[i];
        auto [lj, rj, jj] = lr[j];
        return lj <= ri && ri <= rj;
    };
    vector<int> prv(n);
    for (int i = 0; i < n; ++i) {
        // int ind = -1;
        // for (int j = 0; j < i; ++j) {
        //     if (can(j, i)) {
        //         ind = j;
        //         break;
        //     }
        // }
        // prv[i] = ind;
        auto [l, r, _] = lr[i];
        prv[i] = t.get(l, r + 1);
        t.update(r, {l, i});
    }
    constexpr int k = 2;
    vector<vector<int>> up(k, vector<int>(n, -1));
    up[0] = prv;
    for (int i = 1; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            if (up[i - 1][j] != -1) {
                up[i][j] = up[i - 1][up[i - 1][j]];
            }
        }
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        a = p[a];
        b = p[b];
        int ans = 0;
        for (int i = k - 1; i >= 0; --i) {
            if (up[i][b] != -1 && !can(a, up[i][b]) && lr[up[i][b]][0] > lr[a][1]) {
                b = up[i][b];
                ans += (1 << i);
            }
        }
        if (!can(a, b)) {
            b = up[0][b];
            ++ans;
        }
        while (!can(a, b)) {
            if (prv[b] == -1) {
                ans = -1;
                break;
            }
            b = prv[b];
            ++ans;
        }
        if (b == -1 || !can(a, b)) {
            ans = -1;
        } else if (a != b) {
            ++ans;
        }
        if (ans == -1) {
            cout << "impossible\n";
        } else {
            cout << ans << "\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1583 ms 7476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 364 ms 1284 KB Output is correct
20 Correct 1069 ms 1088 KB Output is correct
21 Correct 386 ms 1360 KB Output is correct
22 Correct 28 ms 1432 KB Output is correct
23 Correct 25 ms 1464 KB Output is correct
24 Correct 23 ms 1472 KB Output is correct
25 Correct 44 ms 1132 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 98 ms 7360 KB Output is correct
20 Correct 86 ms 7396 KB Output is correct
21 Correct 93 ms 7484 KB Output is correct
22 Correct 82 ms 8624 KB Output is correct
23 Correct 93 ms 10600 KB Output is correct
24 Correct 107 ms 10612 KB Output is correct
25 Correct 30 ms 4288 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 7400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1583 ms 7476 KB Time limit exceeded
3 Halted 0 ms 0 KB -