제출 #860594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860594		E869120	Event Hopping (BOI22_events)	C++14	100 / 100	321 ms	26856 KiB

events

#include <bits/stdc++.h>
using namespace std;

class RangeMin {
    public:
    int size_ = 1;
    vector<pair<int, int>> dat;

    void init(int sz) {
        while (size_ <= sz) size_ *= 2;
        dat.resize(size_ * 2, make_pair(0, 0));
    }

    void update(int pos, pair<int, int> val) {
        pos += size_;
        dat[pos] = val;
        while (pos >= 2) {
            pos >>= 1;
            dat[pos] = min(dat[pos * 2 + 0], dat[pos * 2 + 1]);
        }
    }

    pair<int, int> query_(int l, int r, int a, int b, int u) {
        if (l <= a && b <= r) return dat[u];
        if (r <= a || b <= l) return make_pair(2000000000, -1);
        pair<int, int> v1 = query_(l, r, a, (a + b) / 2, u * 2 + 0);
        pair<int, int> v2 = query_(l, r, (a + b) / 2, b, u * 2 + 1);
        return min(v1, v2);
    }

    pair<int, int> query(int l, int r) {
        return query_(l, r, 0, size_, 1);
    }
};

int N, S[1 << 19], T[1 << 19];
int Q, X[1 << 19], Y[1 << 19];
int Prev[1 << 19][22];

int solve(int stt, int goa) {
    if (T[stt] > T[goa]) return -1;
    if (stt == goa) return 0;
    if (T[stt] >= S[goa]) return 1;

    // Doubling
    int cx = goa, cur = 0;
    for (int d = 21; d >= 0; d--) {
        int nex = Prev[cx][d];
        if (S[nex] > T[stt]) { cx = nex; cur += (1 << d); }
    }
    if (cur >= (1 << 21)) return -1;
    return cur + 2;
}

int main() {
    // Step 1. Input
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) cin >> S[i] >> T[i];
    for (int i = 1; i <= Q; i++) cin >> X[i] >> Y[i];

    // Step 2. Sorting
    vector<tuple<int, int, int>> List;
    for (int i = 1; i <= N; i++) List.push_back(make_tuple(T[i], S[i], i));
    sort(List.begin(), List.end());
    RangeMin Z; Z.init(List.size() + 2);
    for (int i = 0; i < (int)List.size(); i++) {
        Z.update(i, make_pair(get<1>(List[i]), get<2>(List[i])));
    }

    // Step 3. Get Prev
    for (int i = 0; i < (int)List.size(); i++) {
        int idx = get<2>(List[i]);
        int pos1 = lower_bound(List.begin(), List.end(), make_tuple(S[idx], -1, -1)) - List.begin();
        pair<int, int> ret = Z.query(pos1, i);
        if (ret.first == 2000000000) Prev[idx][0] = idx;
        else Prev[idx][0] = ret.second;
    }

    // Step 4. Doubling
    for (int d = 1; d <= 21; d++) {
        for (int i = 1; i <= N; i++) Prev[i][d] = Prev[Prev[i][d - 1]][d - 1];
    }

    // Step 5. Answer Query
    for (int i = 1; i <= Q; i++) {
        int ret = solve(X[i], Y[i]);
        if (ret == -1) cout << "impossible" << endl;
        else cout << ret << endl;
    }
    return 0;
}

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