제출 #746043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
746043		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	235 ms	73984 KiB

events

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, q, mx, nxt, A, B, a, b, ans;
vector <int> s(1e5 + 1, 0);
vector <int> e(1e5 + 1, 0);
map<int, int> cc;
vector <int> L(2e5, 2e5);
vector <int> l(2e5, 2e5);
vector <vector <int>> r(2e5, vector <int>(20, 0));

int lift() {
    int ret = 0;
    for (int j = 19; j >= 0; j--) {
        if (r[a][j] >= b) continue;
        a = r[a][j];
        ret += (1 << j);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> e[i];
        cc[s[i]] = cc[e[i]] = 0;
    }
    nxt = 0;
    for (auto p : cc) cc[p.first] = nxt++;
    for (int i = 1; i <= n; i++) {
        s[i] = cc[s[i]];
        e[i] = cc[e[i]];
        mx = max(mx, e[i]);
    }

    for (int i = 0; i <= mx; i++) L[i] = i;
    for (int i = 1; i <= n; i++) L[e[i]] = min(L[e[i]], s[i]);
    l = L;
    for (int i = mx - 1; i >= 0; i--) l[i] = min(l[i], l[i + 1]);

    nxt = 0;
    for (int i = 0; i <= mx; i++) {
        while (l[nxt] <= i) nxt++;
        r[i][0] = nxt - 1;
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i <= mx; i++) {
            r[i][j] = r[r[i][j - 1]][j - 1];
        }
    }

    /*cout << endl << endl;
    for (int i = 0; i <= mx; i++) cout << l[i] << " ";
    cout << endl << endl;
    for (int i = 0; i <= mx; i++) cout << r[i][0] << " ";
    cout << endl << endl;
    for (int j = 0; j < 4; j++) {
        cout << endl;
        for (int i = 0; i <= mx; i++) {
            cout << r[i][j] << " ";
        }
    }
    cout << endl << endl;*/

    for (int i = 0; i < q; i++) {
        cin >> A >> B;
        if (A == B) { cout << "0\n"; continue; }
        if (e[A] == e[B]) { cout << "1\n"; continue; }
        if (e[A] > e[B]) { cout << "impossible\n"; continue; }

        a = e[A]; b = e[B];
        ans = lift();
        if (a < L[e[B]]) { cout << "impossible\n"; continue; }
        if (a < s[B]) { cout << ans + 2 << "\n"; continue; }
        cout << ans + 1 << "\n";
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30