oj.uz

Submission #746045

# Submission time Handle Problem Language Result Execution time Memory
746045 2023-05-21T10:48:59 Z vjudge1 Event Hopping (BOI22_events) C++17
30 / 100
 370 ms 53716 KB 
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, q, mx, nxt, A, B, a, b, ans;
vector <int> s(3e5, 0);
vector <int> e(3e5, 0);
map<int, int> cc;
vector <int> L(3e5, 2e5);
vector <int> l(3e5, 2e5);
vector <vector <int>> r(3e5, vector <int>(20, 0));

int lift() {
    int ret = 0;
    for (int j = 19; j >= 0; j--) {
        if (r[a][j] >= b) continue;
        a = r[a][j];
        ret += (1 << j);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> e[i];
        cc[s[i]] = cc[e[i]] = 0;
    }
    nxt = 0;
    for (auto p : cc) cc[p.first] = nxt++;
    for (int i = 1; i <= n; i++) {
        s[i] = cc[s[i]];
        e[i] = cc[e[i]];
        mx = max(mx, e[i]);
    }

    for (int i = 0; i <= mx; i++) L[i] = i;
    for (int i = 1; i <= n; i++) L[e[i]] = min(L[e[i]], s[i]);
    l = L;
    for (int i = mx - 1; i >= 0; i--) l[i] = min(l[i], l[i + 1]);

    nxt = 0;
    for (int i = 0; i <= mx; i++) {
        while (l[nxt] <= i) nxt++;
        r[i][0] = nxt - 1;
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i <= mx; i++) {
            r[i][j] = r[r[i][j - 1]][j - 1];
        }
    }

    /*cout << endl << endl;
    for (int i = 0; i <= mx; i++) cout << l[i] << " ";
    cout << endl << endl;
    for (int i = 0; i <= mx; i++) cout << r[i][0] << " ";
    cout << endl << endl;
    for (int j = 0; j < 4; j++) {
        cout << endl;
        for (int i = 0; i <= mx; i++) {
            cout << r[i][j] << " ";
        }
    }
    cout << endl << endl;*/

    for (int i = 0; i < q; i++) {
        cin >> A >> B;
        if (A == B) { cout << "0\n"; continue; }
        if (e[A] == e[B]) { cout << "1\n"; continue; }
        if (e[A] > e[B]) { cout << "impossible\n"; continue; }

        a = e[A]; b = e[B];
        ans = lift();
        if (a < L[e[B]]) { cout << "impossible\n"; continue; }
        if (a < s[B]) { cout << ans + 2 << "\n"; continue; }
        cout << ans + 1 << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 40140 KB Output is correct
2 Correct 184 ms 45536 KB Output is correct
3 Correct 180 ms 45472 KB Output is correct
4 Correct 175 ms 45520 KB Output is correct
5 Correct 178 ms 45968 KB Output is correct
6 Correct 198 ms 46472 KB Output is correct
7 Correct 199 ms 46672 KB Output is correct
8 Correct 225 ms 50652 KB Output is correct
9 Correct 278 ms 51560 KB Output is correct
10 Correct 222 ms 48936 KB Output is correct
11 Correct 234 ms 50856 KB Output is correct
12 Correct 138 ms 48372 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40256 KB Output is correct
2 Correct 29 ms 40340 KB Output is correct
3 Correct 37 ms 40268 KB Output is correct
4 Correct 29 ms 40276 KB Output is correct
5 Incorrect 29 ms 40264 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40256 KB Output is correct
2 Correct 29 ms 40340 KB Output is correct
3 Correct 37 ms 40268 KB Output is correct
4 Correct 29 ms 40276 KB Output is correct
5 Incorrect 29 ms 40264 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40256 KB Output is correct
2 Correct 29 ms 40340 KB Output is correct
3 Correct 37 ms 40268 KB Output is correct
4 Correct 29 ms 40276 KB Output is correct
5 Incorrect 29 ms 40264 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 187 ms 45448 KB Output is correct
2 Correct 191 ms 45600 KB Output is correct
3 Correct 194 ms 45472 KB Output is correct
4 Correct 240 ms 51660 KB Output is correct
5 Correct 205 ms 48916 KB Output is correct
6 Correct 370 ms 53452 KB Output is correct
7 Correct 314 ms 53408 KB Output is correct
8 Correct 294 ms 53716 KB Output is correct
9 Correct 267 ms 51560 KB Output is correct
10 Correct 317 ms 52992 KB Output is correct
11 Correct 311 ms 52792 KB Output is correct
12 Correct 273 ms 53028 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 40140 KB Output is correct
2 Correct 184 ms 45536 KB Output is correct
3 Correct 180 ms 45472 KB Output is correct
4 Correct 175 ms 45520 KB Output is correct
5 Correct 178 ms 45968 KB Output is correct
6 Correct 198 ms 46472 KB Output is correct
7 Correct 199 ms 46672 KB Output is correct
8 Correct 225 ms 50652 KB Output is correct
9 Correct 278 ms 51560 KB Output is correct
10 Correct 222 ms 48936 KB Output is correct
11 Correct 234 ms 50856 KB Output is correct
12 Correct 138 ms 48372 KB Output is correct
13 Correct 35 ms 40256 KB Output is correct
14 Correct 29 ms 40340 KB Output is correct
15 Correct 37 ms 40268 KB Output is correct
16 Correct 29 ms 40276 KB Output is correct
17 Incorrect 29 ms 40264 KB Output isn't correct
18 Halted 0 ms 0 KB -