oj.uz

Submission #762134

# Submission time Handle Problem Language Result Execution time Memory
762134 2023-06-20T22:46:42 Z zsombor Event Hopping (BOI22_events) C++17
20 / 100
 230 ms 33888 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 (ev[a].e == ev[b].e) { cout << "0\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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31572 KB Output is correct
2 Correct 219 ms 33328 KB Output is correct
3 Correct 216 ms 33316 KB Output is correct
4 Correct 228 ms 33340 KB Output is correct
5 Correct 218 ms 33392 KB Output is correct
6 Correct 217 ms 33424 KB Output is correct
7 Correct 213 ms 33384 KB Output is correct
8 Correct 127 ms 33832 KB Output is correct
9 Correct 121 ms 33824 KB Output is correct
10 Correct 156 ms 33688 KB Output is correct
11 Incorrect 155 ms 33732 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31644 KB Output is correct
2 Correct 23 ms 31572 KB Output is correct
3 Correct 27 ms 31588 KB Output is correct
4 Correct 26 ms 31572 KB Output is correct
5 Correct 25 ms 31664 KB Output is correct
6 Incorrect 29 ms 31604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31644 KB Output is correct
2 Correct 23 ms 31572 KB Output is correct
3 Correct 27 ms 31588 KB Output is correct
4 Correct 26 ms 31572 KB Output is correct
5 Correct 25 ms 31664 KB Output is correct
6 Incorrect 29 ms 31604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31644 KB Output is correct
2 Correct 23 ms 31572 KB Output is correct
3 Correct 27 ms 31588 KB Output is correct
4 Correct 26 ms 31572 KB Output is correct
5 Correct 25 ms 31664 KB Output is correct
6 Incorrect 29 ms 31604 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 218 ms 33352 KB Output is correct
2 Correct 219 ms 33372 KB Output is correct
3 Correct 226 ms 33348 KB Output is correct
4 Correct 114 ms 33888 KB Output is correct
5 Correct 205 ms 33692 KB Output is correct
6 Correct 207 ms 33508 KB Output is correct
7 Correct 195 ms 33488 KB Output is correct
8 Correct 163 ms 33568 KB Output is correct
9 Correct 88 ms 32804 KB Output is correct
10 Correct 225 ms 33188 KB Output is correct
11 Correct 199 ms 32948 KB Output is correct
12 Correct 230 ms 33184 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31572 KB Output is correct
2 Correct 219 ms 33328 KB Output is correct
3 Correct 216 ms 33316 KB Output is correct
4 Correct 228 ms 33340 KB Output is correct
5 Correct 218 ms 33392 KB Output is correct
6 Correct 217 ms 33424 KB Output is correct
7 Correct 213 ms 33384 KB Output is correct
8 Correct 127 ms 33832 KB Output is correct
9 Correct 121 ms 33824 KB Output is correct
10 Correct 156 ms 33688 KB Output is correct
11 Incorrect 155 ms 33732 KB Output isn't correct
12 Halted 0 ms 0 KB -