oj.uz

Submission #762108

# Submission time Handle Problem Language Result Execution time Memory
762108 2023-06-20T20:25:39 Z zsombor Event Hopping (BOI22_events) C++17
20 / 100
 246 ms 33840 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 bs(int val) {
    int a = -1, b = n - 1, c;
    while (b - a > 1) {
        c = (a + b) / 2;
        (ev[c].e < val ? a = c : b = c);
    }
    return b;
}

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, 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++) {
        lift[i][0] = bs(ev[i].s);
        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 < (1 << 17)) cout << ans << endl;
        else cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31572 KB Output is correct
2 Correct 216 ms 33380 KB Output is correct
3 Correct 218 ms 33372 KB Output is correct
4 Correct 240 ms 33280 KB Output is correct
5 Correct 246 ms 33352 KB Output is correct
6 Correct 223 ms 33448 KB Output is correct
7 Correct 225 ms 33436 KB Output is correct
8 Correct 114 ms 33840 KB Output is correct
9 Correct 119 ms 33820 KB Output is correct
10 Correct 177 ms 33700 KB Output is correct
11 Incorrect 152 ms 33700 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 31576 KB Output is correct
2 Correct 23 ms 31564 KB Output is correct
3 Correct 26 ms 31620 KB Output is correct
4 Correct 34 ms 31644 KB Output is correct
5 Correct 26 ms 31572 KB Output is correct
6 Incorrect 31 ms 31612 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 31576 KB Output is correct
2 Correct 23 ms 31564 KB Output is correct
3 Correct 26 ms 31620 KB Output is correct
4 Correct 34 ms 31644 KB Output is correct
5 Correct 26 ms 31572 KB Output is correct
6 Incorrect 31 ms 31612 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 31576 KB Output is correct
2 Correct 23 ms 31564 KB Output is correct
3 Correct 26 ms 31620 KB Output is correct
4 Correct 34 ms 31644 KB Output is correct
5 Correct 26 ms 31572 KB Output is correct
6 Incorrect 31 ms 31612 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 33316 KB Output is correct
2 Correct 222 ms 33392 KB Output is correct
3 Correct 223 ms 33356 KB Output is correct
4 Correct 112 ms 33824 KB Output is correct
5 Correct 156 ms 33696 KB Output is correct
6 Correct 209 ms 33508 KB Output is correct
7 Correct 200 ms 33456 KB Output is correct
8 Correct 159 ms 33568 KB Output is correct
9 Correct 87 ms 32804 KB Output is correct
10 Correct 228 ms 33128 KB Output is correct
11 Correct 200 ms 32972 KB Output is correct
12 Correct 231 ms 33192 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31572 KB Output is correct
2 Correct 216 ms 33380 KB Output is correct
3 Correct 218 ms 33372 KB Output is correct
4 Correct 240 ms 33280 KB Output is correct
5 Correct 246 ms 33352 KB Output is correct
6 Correct 223 ms 33448 KB Output is correct
7 Correct 225 ms 33436 KB Output is correct
8 Correct 114 ms 33840 KB Output is correct
9 Correct 119 ms 33820 KB Output is correct
10 Correct 177 ms 33700 KB Output is correct
11 Incorrect 152 ms 33700 KB Output isn't correct
12 Halted 0 ms 0 KB -