oj.uz

Submission #746043

# Submission time Handle Problem Language Result Execution time Memory
746043 2023-05-21T10:47:25 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 235 ms 73984 KB 
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, q, mx, nxt, A, B, a, b, ans;
vector <int> s(1e5 + 1, 0);
vector <int> e(1e5 + 1, 0);
map<int, int> cc;
vector <int> L(2e5, 2e5);
vector <int> l(2e5, 2e5);
vector <vector <int>> r(2e5, 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26068 KB Output is correct
2 Correct 173 ms 32320 KB Output is correct
3 Correct 164 ms 34644 KB Output is correct
4 Correct 183 ms 34584 KB Output is correct
5 Correct 173 ms 35004 KB Output is correct
6 Correct 188 ms 35540 KB Output is correct
7 Correct 235 ms 35660 KB Output is correct
8 Correct 214 ms 39624 KB Output is correct
9 Runtime error 179 ms 73984 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26112 KB Output is correct
2 Correct 24 ms 26148 KB Output is correct
3 Correct 19 ms 26164 KB Output is correct
4 Correct 20 ms 26156 KB Output is correct
5 Incorrect 20 ms 26112 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26112 KB Output is correct
2 Correct 24 ms 26148 KB Output is correct
3 Correct 19 ms 26164 KB Output is correct
4 Correct 20 ms 26156 KB Output is correct
5 Incorrect 20 ms 26112 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26112 KB Output is correct
2 Correct 24 ms 26148 KB Output is correct
3 Correct 19 ms 26164 KB Output is correct
4 Correct 20 ms 26156 KB Output is correct
5 Incorrect 20 ms 26112 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 32452 KB Output is correct
2 Correct 163 ms 34536 KB Output is correct
3 Correct 170 ms 34428 KB Output is correct
4 Runtime error 208 ms 73960 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26068 KB Output is correct
2 Correct 173 ms 32320 KB Output is correct
3 Correct 164 ms 34644 KB Output is correct
4 Correct 183 ms 34584 KB Output is correct
5 Correct 173 ms 35004 KB Output is correct
6 Correct 188 ms 35540 KB Output is correct
7 Correct 235 ms 35660 KB Output is correct
8 Correct 214 ms 39624 KB Output is correct
9 Runtime error 179 ms 73984 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -