oj.uz

Submission #762133

# Submission time Handle Problem Language Result Execution time Memory
762133 2023-06-20T22:36:24 Z zsombor Event Hopping (BOI22_events) C++17
20 / 100
 249 ms 34192 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 < 1e5) cout << ans << endl;
        else cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31652 KB Output is correct
2 Correct 246 ms 33544 KB Output is correct
3 Correct 222 ms 33600 KB Output is correct
4 Correct 230 ms 33540 KB Output is correct
5 Correct 222 ms 33796 KB Output is correct
6 Correct 232 ms 33740 KB Output is correct
7 Correct 219 ms 33760 KB Output is correct
8 Correct 115 ms 34192 KB Output is correct
9 Correct 123 ms 34092 KB Output is correct
10 Correct 161 ms 33956 KB Output is correct
11 Incorrect 156 ms 33952 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 31572 KB Output is correct
2 Correct 23 ms 31656 KB Output is correct
3 Correct 26 ms 31660 KB Output is correct
4 Correct 27 ms 31556 KB Output is correct
5 Correct 26 ms 31668 KB Output is correct
6 Incorrect 27 ms 31616 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 31572 KB Output is correct
2 Correct 23 ms 31656 KB Output is correct
3 Correct 26 ms 31660 KB Output is correct
4 Correct 27 ms 31556 KB Output is correct
5 Correct 26 ms 31668 KB Output is correct
6 Incorrect 27 ms 31616 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 31572 KB Output is correct
2 Correct 23 ms 31656 KB Output is correct
3 Correct 26 ms 31660 KB Output is correct
4 Correct 27 ms 31556 KB Output is correct
5 Correct 26 ms 31668 KB Output is correct
6 Incorrect 27 ms 31616 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 223 ms 33728 KB Output is correct
2 Correct 218 ms 33572 KB Output is correct
3 Correct 225 ms 33540 KB Output is correct
4 Correct 115 ms 34160 KB Output is correct
5 Correct 159 ms 33956 KB Output is correct
6 Correct 201 ms 33700 KB Output is correct
7 Correct 249 ms 33756 KB Output is correct
8 Correct 161 ms 33948 KB Output is correct
9 Correct 86 ms 33068 KB Output is correct
10 Correct 228 ms 33456 KB Output is correct
11 Correct 201 ms 33248 KB Output is correct
12 Correct 233 ms 33456 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31652 KB Output is correct
2 Correct 246 ms 33544 KB Output is correct
3 Correct 222 ms 33600 KB Output is correct
4 Correct 230 ms 33540 KB Output is correct
5 Correct 222 ms 33796 KB Output is correct
6 Correct 232 ms 33740 KB Output is correct
7 Correct 219 ms 33760 KB Output is correct
8 Correct 115 ms 34192 KB Output is correct
9 Correct 123 ms 34092 KB Output is correct
10 Correct 161 ms 33956 KB Output is correct
11 Incorrect 156 ms 33952 KB Output isn't correct
12 Halted 0 ms 0 KB -