oj.uz

Submission #850042

# Submission time Handle Problem Language Result Execution time Memory
850042 2023-09-15T16:44:00 Z MinaRagy06 Event Hopping (BOI22_events) C++17
30 / 100
 236 ms 55244 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 = 20, 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 117 ms 45860 KB Output is correct
3 Correct 154 ms 46064 KB Output is correct
4 Correct 132 ms 46024 KB Output is correct
5 Correct 133 ms 46396 KB Output is correct
6 Correct 149 ms 50020 KB Output is correct
7 Correct 146 ms 50376 KB Output is correct
8 Correct 179 ms 54540 KB Output is correct
9 Correct 225 ms 54728 KB Output is correct
10 Correct 195 ms 49564 KB Output is correct
11 Correct 219 ms 51424 KB Output is correct
12 Correct 160 ms 45608 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 33368 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 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 33368 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 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 33368 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 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 117 ms 46024 KB Output is correct
2 Correct 124 ms 46024 KB Output is correct
3 Correct 140 ms 46024 KB Output is correct
4 Correct 227 ms 51656 KB Output is correct
5 Correct 198 ms 46284 KB Output is correct
6 Correct 236 ms 51300 KB Output is correct
7 Correct 220 ms 51268 KB Output is correct
8 Correct 218 ms 51396 KB Output is correct
9 Correct 144 ms 55244 KB Output is correct
10 Correct 166 ms 50904 KB Output is correct
11 Correct 183 ms 51964 KB Output is correct
12 Correct 164 ms 50884 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 117 ms 45860 KB Output is correct
3 Correct 154 ms 46064 KB Output is correct
4 Correct 132 ms 46024 KB Output is correct
5 Correct 133 ms 46396 KB Output is correct
6 Correct 149 ms 50020 KB Output is correct
7 Correct 146 ms 50376 KB Output is correct
8 Correct 179 ms 54540 KB Output is correct
9 Correct 225 ms 54728 KB Output is correct
10 Correct 195 ms 49564 KB Output is correct
11 Correct 219 ms 51424 KB Output is correct
12 Correct 160 ms 45608 KB Output is correct
13 Correct 6 ms 33368 KB Output is correct
14 Correct 6 ms 33368 KB Output is correct
15 Correct 7 ms 33368 KB Output is correct
16 Correct 7 ms 33368 KB Output is correct
17 Incorrect 7 ms 33368 KB Output isn't correct
18 Halted 0 ms 0 KB -