oj.uz

Submission #644803

# Submission time Handle Problem Language Result Execution time Memory
644803 2022-09-25T09:29:10 Z FedShat Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 11388 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});
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        a = p[a];
        b = p[b];
        int ans = 0;
        while (!can(a, b)) {
            if (prv[b] == -1) {
                ans = -1;
                break;
            }
            b = prv[b];
            ++ans;
        }
        if (a != b && ans != -1) {
            ++ans;
        }
        if (ans == -1) {
            cout << "impossible\n";
        } else {
            cout << ans << "\n";
        }
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 368 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 328 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 368 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 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 1 ms 328 KB Output is correct
16 Correct 2 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 362 ms 1228 KB Output is correct
20 Correct 1031 ms 1308 KB Output is correct
21 Correct 382 ms 1492 KB Output is correct
22 Correct 25 ms 1484 KB Output is correct
23 Correct 26 ms 1484 KB Output is correct
24 Correct 24 ms 1492 KB Output is correct
25 Correct 40 ms 1240 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 368 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 328 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 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 92 ms 6216 KB Output is correct
20 Correct 79 ms 7272 KB Output is correct
21 Correct 92 ms 8052 KB Output is correct
22 Correct 87 ms 9232 KB Output is correct
23 Correct 89 ms 11272 KB Output is correct
24 Correct 90 ms 11388 KB Output is correct
25 Correct 29 ms 4292 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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