oj.uz

Submission #746072

# Submission time Handle Problem Language Result Execution time Memory
746072 2023-05-21T11:01:12 Z vjudge1 Event Hopping (BOI22_events) C++17
30 / 100
 390 ms 82116 KB 
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ll = long long;

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

ll lift() {
    ll ret = 0;
    for (ll 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 (ll 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 (ll i = 1; i <= n; i++) {
        s[i] = cc[s[i]];
        e[i] = cc[e[i]];
        mx = max(mx, e[i]);
    }

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

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

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

    for (ll 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 39 ms 68308 KB Output is correct
2 Correct 192 ms 75316 KB Output is correct
3 Correct 188 ms 75276 KB Output is correct
4 Correct 281 ms 75224 KB Output is correct
5 Correct 202 ms 75848 KB Output is correct
6 Correct 207 ms 76492 KB Output is correct
7 Correct 226 ms 76808 KB Output is correct
8 Correct 252 ms 81964 KB Output is correct
9 Correct 281 ms 81984 KB Output is correct
10 Correct 234 ms 75560 KB Output is correct
11 Correct 253 ms 78088 KB Output is correct
12 Correct 172 ms 75808 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68372 KB Output is correct
2 Correct 42 ms 68308 KB Output is correct
3 Correct 42 ms 68376 KB Output is correct
4 Correct 42 ms 68380 KB Output is correct
5 Incorrect 44 ms 68376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68372 KB Output is correct
2 Correct 42 ms 68308 KB Output is correct
3 Correct 42 ms 68376 KB Output is correct
4 Correct 42 ms 68380 KB Output is correct
5 Incorrect 44 ms 68376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68372 KB Output is correct
2 Correct 42 ms 68308 KB Output is correct
3 Correct 42 ms 68376 KB Output is correct
4 Correct 42 ms 68380 KB Output is correct
5 Incorrect 44 ms 68376 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 215 ms 75252 KB Output is correct
2 Correct 200 ms 75212 KB Output is correct
3 Correct 213 ms 75260 KB Output is correct
4 Correct 274 ms 82116 KB Output is correct
5 Correct 234 ms 75584 KB Output is correct
6 Correct 390 ms 81664 KB Output is correct
7 Correct 354 ms 81580 KB Output is correct
8 Correct 329 ms 81808 KB Output is correct
9 Correct 243 ms 80832 KB Output is correct
10 Correct 315 ms 81324 KB Output is correct
11 Correct 309 ms 81136 KB Output is correct
12 Correct 306 ms 81300 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68308 KB Output is correct
2 Correct 192 ms 75316 KB Output is correct
3 Correct 188 ms 75276 KB Output is correct
4 Correct 281 ms 75224 KB Output is correct
5 Correct 202 ms 75848 KB Output is correct
6 Correct 207 ms 76492 KB Output is correct
7 Correct 226 ms 76808 KB Output is correct
8 Correct 252 ms 81964 KB Output is correct
9 Correct 281 ms 81984 KB Output is correct
10 Correct 234 ms 75560 KB Output is correct
11 Correct 253 ms 78088 KB Output is correct
12 Correct 172 ms 75808 KB Output is correct
13 Correct 39 ms 68372 KB Output is correct
14 Correct 42 ms 68308 KB Output is correct
15 Correct 42 ms 68376 KB Output is correct
16 Correct 42 ms 68380 KB Output is correct
17 Incorrect 44 ms 68376 KB Output isn't correct
18 Halted 0 ms 0 KB -