oj.uz

Submission #762384

# Submission time Handle Problem Language Result Execution time Memory
762384 2023-06-21T11:10:12 Z zsombor Event Hopping (BOI22_events) C++17
30 / 100
 268 ms 36448 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct event {
    int s, e, ind;
};

int n, q;
vector <event> ev;
vector <int> new_ind(1e5 + 1);
vector <int> Log(1e5 + 1, 0);
vector <vector <int>> st(2e5, vector<int>(17));
vector <vector <int>> lift(1e5, vector<int>(17));

bool srt(event a, event b) {
    if (a.e < b.e) return true;
    if (a.e > b.e) return false;
    return (a.s < b.s ? true : false);
}

int mini(int a, int b) {
    return (ev[a].s < ev[b].s ? a : b);
}

int range_mini(int l, int r) {
    int j = Log[r - l + 1];
    return mini(st[l][j], st[r - (1 << j) + 1][j]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b, c, ans;
    cin >> n >> q;
    ev.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> ev[i].s >> ev[i].e;
        ev[i].ind = i + 1;
    }
    sort(ev.begin(), ev.end(), srt);
    for (int i = 0; i < n; i++) new_ind[ev[i].ind] = i;

    for (int i = 2; i <= 1e5; i++) Log[i] = Log[i / 2] + 1;
    for (int i = 0; i < n; i++) st[i][0] = i;
    for (int i = n; i < 2e5; i++) fill(st[i].begin(), st[i].end(), n - 1);
    for (int j = 1; j < 17; j++) {
        for (int i = 0; i < n; i++) {
            st[i][j] = mini(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    for (int i = 0; i < n; i++) {
        a = -1; b = i;
        while (b - a > 1) {
            c = (a + b) / 2;
            (ev[c].e < ev[i].s ? a = c : b = c);
        }
        lift[i][0] = b;
        for (int j = 1; j < 17; j++) {
            a = range_mini(lift[i][j - 1], i);
            lift[i][j] = lift[a][j - 1];
        }
    }

    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        a = new_ind[a];
        b = new_ind[b];
        if (a == b) { cout << "0\n"; continue; }
        if (ev[a].e == ev[b].e) { cout << "1\n"; continue; }
        if (a > b) { cout << "impossible\n"; continue; }
        ans = 0;
        for (int j = 16; j >= 0; j--) {
            if (lift[b][j] <= a) continue;
            b = lift[b][j];
            ans += (1 << j);
        }
        ans++;
        if (ans < 1e5) cout << ans << endl;
        else cout << "impossible\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31652 KB Output is correct
2 Correct 237 ms 35920 KB Output is correct
3 Correct 244 ms 35968 KB Output is correct
4 Correct 247 ms 35940 KB Output is correct
5 Correct 237 ms 36112 KB Output is correct
6 Correct 248 ms 36016 KB Output is correct
7 Correct 218 ms 36044 KB Output is correct
8 Correct 129 ms 36448 KB Output is correct
9 Correct 115 ms 36348 KB Output is correct
10 Correct 165 ms 36240 KB Output is correct
11 Correct 182 ms 36328 KB Output is correct
12 Correct 115 ms 36244 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31564 KB Output is correct
2 Correct 23 ms 31528 KB Output is correct
3 Correct 27 ms 31656 KB Output is correct
4 Correct 26 ms 31664 KB Output is correct
5 Correct 26 ms 31576 KB Output is correct
6 Incorrect 27 ms 31648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31564 KB Output is correct
2 Correct 23 ms 31528 KB Output is correct
3 Correct 27 ms 31656 KB Output is correct
4 Correct 26 ms 31664 KB Output is correct
5 Correct 26 ms 31576 KB Output is correct
6 Incorrect 27 ms 31648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31564 KB Output is correct
2 Correct 23 ms 31528 KB Output is correct
3 Correct 27 ms 31656 KB Output is correct
4 Correct 26 ms 31664 KB Output is correct
5 Correct 26 ms 31576 KB Output is correct
6 Incorrect 27 ms 31648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 36032 KB Output is correct
2 Correct 220 ms 35856 KB Output is correct
3 Correct 246 ms 35848 KB Output is correct
4 Correct 119 ms 36420 KB Output is correct
5 Correct 180 ms 36256 KB Output is correct
6 Correct 210 ms 36044 KB Output is correct
7 Correct 217 ms 36024 KB Output is correct
8 Correct 181 ms 36192 KB Output is correct
9 Correct 87 ms 34708 KB Output is correct
10 Correct 251 ms 35756 KB Output is correct
11 Correct 202 ms 35472 KB Output is correct
12 Correct 268 ms 35724 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31652 KB Output is correct
2 Correct 237 ms 35920 KB Output is correct
3 Correct 244 ms 35968 KB Output is correct
4 Correct 247 ms 35940 KB Output is correct
5 Correct 237 ms 36112 KB Output is correct
6 Correct 248 ms 36016 KB Output is correct
7 Correct 218 ms 36044 KB Output is correct
8 Correct 129 ms 36448 KB Output is correct
9 Correct 115 ms 36348 KB Output is correct
10 Correct 165 ms 36240 KB Output is correct
11 Correct 182 ms 36328 KB Output is correct
12 Correct 115 ms 36244 KB Output is correct
13 Correct 24 ms 31564 KB Output is correct
14 Correct 23 ms 31528 KB Output is correct
15 Correct 27 ms 31656 KB Output is correct
16 Correct 26 ms 31664 KB Output is correct
17 Correct 26 ms 31576 KB Output is correct
18 Incorrect 27 ms 31648 KB Output isn't correct
19 Halted 0 ms 0 KB -