oj.uz

Submission #850060

# Submission time Handle Problem Language Result Execution time Memory
850060 2023-09-15T17:00:35 Z MinaRagy06 Event Hopping (BOI22_events) C++17
30 / 100
 180 ms 55004 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;
        }
        if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
            cout << "1\n";
            continue;
        }
        int ans = 0;
        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 (!(a[e][0] <= a[s][1] && a[s][1] <= a[e][1])) {
            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 45876 KB Output is correct
3 Correct 131 ms 45896 KB Output is correct
4 Correct 150 ms 45992 KB Output is correct
5 Correct 124 ms 46540 KB Output is correct
6 Correct 140 ms 47056 KB Output is correct
7 Correct 125 ms 47304 KB Output is correct
8 Correct 147 ms 51520 KB Output is correct
9 Correct 149 ms 51512 KB Output is correct
10 Correct 126 ms 46332 KB Output is correct
11 Correct 161 ms 48764 KB Output is correct
12 Correct 80 ms 43212 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 33572 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Incorrect 6 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 33572 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Incorrect 6 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 33572 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Incorrect 6 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 122 ms 46216 KB Output is correct
2 Correct 121 ms 46024 KB Output is correct
3 Correct 151 ms 45956 KB Output is correct
4 Correct 161 ms 51652 KB Output is correct
5 Correct 134 ms 46320 KB Output is correct
6 Correct 165 ms 51140 KB Output is correct
7 Correct 180 ms 51336 KB Output is correct
8 Correct 163 ms 51396 KB Output is correct
9 Correct 167 ms 55004 KB Output is correct
10 Correct 167 ms 50892 KB Output is correct
11 Correct 170 ms 51912 KB Output is correct
12 Correct 170 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 127 ms 45876 KB Output is correct
3 Correct 131 ms 45896 KB Output is correct
4 Correct 150 ms 45992 KB Output is correct
5 Correct 124 ms 46540 KB Output is correct
6 Correct 140 ms 47056 KB Output is correct
7 Correct 125 ms 47304 KB Output is correct
8 Correct 147 ms 51520 KB Output is correct
9 Correct 149 ms 51512 KB Output is correct
10 Correct 126 ms 46332 KB Output is correct
11 Correct 161 ms 48764 KB Output is correct
12 Correct 80 ms 43212 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 33572 KB Output is correct
16 Correct 7 ms 33368 KB Output is correct
17 Incorrect 6 ms 33368 KB Output isn't correct
18 Halted 0 ms 0 KB -