oj.uz

Submission #850049

# Submission time Handle Problem Language Result Execution time Memory
850049 2023-09-15T16:52:29 Z MinaRagy06 Event Hopping (BOI22_events) C++17
30 / 100
 192 ms 55240 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
 
const int N = 200'005;
array<int, 2> a[N];
int bl[18][N];
vector<array<int, 2>> st[2 * N], en[2 * N];
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    set<int> times;
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        times.insert(a[i][0]), times.insert(a[i][1]);
    }
    vector<int> v;
    for (auto i : times) {
        v.push_back(i);
    }
    for (int i = 0; i < n; i++) {
        st[lower_bound(v.begin(), v.end(), a[i][0]) - v.begin()].push_back({i, a[i][1]});
        en[lower_bound(v.begin(), v.end(), a[i][1]) - v.begin()].push_back({i, a[i][1]});
    }
    multiset<array<int, 2>> s;
    for (int i = v.size() - 1; i >= 0; i--) {
        for (auto [idx, t] : en[i]) {
            s.insert({-t, idx});
        }
        for (auto [idx, t] : en[i]) {
            bl[0][idx] = (*s.begin())[1];
        }
        for (auto [idx, t] : st[i]) {
            s.erase(s.find({-t, idx}));
        }
    }
    for (int j = 1; j < 18; j++) {
        for (int i = 0; i < n; i++) {
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
        }
    }
    while (q--) {
        int s, e;
        cin >> s >> e;
        s--, e--;
        if (s == e) {
            cout << "0\n";
            continue;
        }
        int cnt = 2, ans = 0, ok = 0;
        while (cnt--) {
            if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
                ok = 1;
                break;
            }
            for (int j = 17; j >= 0; j--) {
                int New = bl[j][s];
                if (!(a[e][0] <= a[New][1] && a[New][1] <= a[e][1]) && a[New][1] <= a[e][1]) {
                    s = New;
                    ans += (1 << j);
                }
            }
            ans++;
            s = bl[0][s];
        }
        if (!ok) {
            cout << "impossible\n";
            continue;
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 127 ms 46024 KB Output is correct
3 Correct 122 ms 45844 KB Output is correct
4 Correct 148 ms 46024 KB Output is correct
5 Correct 141 ms 46448 KB Output is correct
6 Correct 135 ms 47084 KB Output is correct
7 Correct 139 ms 47304 KB Output is correct
8 Correct 150 ms 51616 KB Output is correct
9 Correct 169 ms 51652 KB Output is correct
10 Correct 155 ms 46276 KB Output is correct
11 Correct 139 ms 48476 KB Output is correct
12 Correct 85 ms 43288 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 45864 KB Output is correct
2 Correct 124 ms 46024 KB Output is correct
3 Correct 145 ms 46080 KB Output is correct
4 Correct 182 ms 51648 KB Output is correct
5 Correct 132 ms 46336 KB Output is correct
6 Correct 185 ms 51144 KB Output is correct
7 Correct 168 ms 51144 KB Output is correct
8 Correct 188 ms 51316 KB Output is correct
9 Correct 153 ms 55240 KB Output is correct
10 Correct 191 ms 50796 KB Output is correct
11 Correct 178 ms 51912 KB Output is correct
12 Correct 192 ms 50944 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 127 ms 46024 KB Output is correct
3 Correct 122 ms 45844 KB Output is correct
4 Correct 148 ms 46024 KB Output is correct
5 Correct 141 ms 46448 KB Output is correct
6 Correct 135 ms 47084 KB Output is correct
7 Correct 139 ms 47304 KB Output is correct
8 Correct 150 ms 51616 KB Output is correct
9 Correct 169 ms 51652 KB Output is correct
10 Correct 155 ms 46276 KB Output is correct
11 Correct 139 ms 48476 KB Output is correct
12 Correct 85 ms 43288 KB Output is correct
13 Correct 6 ms 33368 KB Output is correct
14 Correct 6 ms 33372 KB Output is correct
15 Correct 7 ms 33624 KB Output is correct
16 Correct 8 ms 33368 KB Output is correct
17 Incorrect 7 ms 33368 KB Output isn't correct
18 Halted 0 ms 0 KB -