oj.uz

Submission #746075

# Submission time Handle Problem Language Result Execution time Memory
746075 2023-05-21T11:21:03 Z zsombor Event Hopping (BOI22_events) C++17
30 / 100
 337 ms 50712 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, 3e5);
vector <int> l(3e5, 3e5);
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 28 ms 40204 KB Output is correct
2 Correct 171 ms 45448 KB Output is correct
3 Correct 194 ms 45448 KB Output is correct
4 Correct 219 ms 45452 KB Output is correct
5 Correct 196 ms 46008 KB Output is correct
6 Correct 199 ms 46452 KB Output is correct
7 Correct 209 ms 46748 KB Output is correct
8 Correct 242 ms 50652 KB Output is correct
9 Correct 246 ms 50656 KB Output is correct
10 Correct 235 ms 45820 KB Output is correct
11 Correct 260 ms 47792 KB Output is correct
12 Correct 135 ms 45924 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 40176 KB Output is correct
2 Correct 28 ms 40284 KB Output is correct
3 Correct 32 ms 40288 KB Output is correct
4 Correct 30 ms 40276 KB Output is correct
5 Incorrect 37 ms 40216 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 40176 KB Output is correct
2 Correct 28 ms 40284 KB Output is correct
3 Correct 32 ms 40288 KB Output is correct
4 Correct 30 ms 40276 KB Output is correct
5 Incorrect 37 ms 40216 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 40176 KB Output is correct
2 Correct 28 ms 40284 KB Output is correct
3 Correct 32 ms 40288 KB Output is correct
4 Correct 30 ms 40276 KB Output is correct
5 Incorrect 37 ms 40216 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 167 ms 45444 KB Output is correct
2 Correct 190 ms 45520 KB Output is correct
3 Correct 188 ms 45484 KB Output is correct
4 Correct 236 ms 50712 KB Output is correct
5 Correct 214 ms 45824 KB Output is correct
6 Correct 291 ms 50380 KB Output is correct
7 Correct 337 ms 50344 KB Output is correct
8 Correct 313 ms 50496 KB Output is correct
9 Correct 202 ms 49684 KB Output is correct
10 Correct 278 ms 49972 KB Output is correct
11 Correct 260 ms 49760 KB Output is correct
12 Correct 268 ms 50016 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 40204 KB Output is correct
2 Correct 171 ms 45448 KB Output is correct
3 Correct 194 ms 45448 KB Output is correct
4 Correct 219 ms 45452 KB Output is correct
5 Correct 196 ms 46008 KB Output is correct
6 Correct 199 ms 46452 KB Output is correct
7 Correct 209 ms 46748 KB Output is correct
8 Correct 242 ms 50652 KB Output is correct
9 Correct 246 ms 50656 KB Output is correct
10 Correct 235 ms 45820 KB Output is correct
11 Correct 260 ms 47792 KB Output is correct
12 Correct 135 ms 45924 KB Output is correct
13 Correct 31 ms 40176 KB Output is correct
14 Correct 28 ms 40284 KB Output is correct
15 Correct 32 ms 40288 KB Output is correct
16 Correct 30 ms 40276 KB Output is correct
17 Incorrect 37 ms 40216 KB Output isn't correct
18 Halted 0 ms 0 KB -