Submission #762384

#	Time	Username	Problem	Language	Result	Execution time	Memory
762384		zsombor	Event Hopping (BOI22_events)	C++17	30 / 100	268 ms	36448 KiB

events

#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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30