제출 #579618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579618		Josia	Event Hopping (BOI22_events)	C++17	40 / 100	1601 ms	37964 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define int int64_t



struct seg {
    vector<pair<int, int>> tree;

    seg(int n) {
        tree.assign(n*4, {1e18, -1});
    }

    void update(int v, int rl, int rr, int pos, pair<int, int> x) {
        if (rl == rr) {
            tree[v] = x;
            return;
        }
        int rm = (rl + rr) / 2;

        if (pos <= rm) update(v*2, rl, rm, pos, x);
        else update(v*2+1, rm+1, rr, pos, x);

        tree[v] = min(tree[v*2], tree[v*2+1]);
    }

    pair<int, int> query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return {1e18, -1};
        if (rl == ql && rr == qr) return tree[v];

        int rm = (rl + rr) / 2;

        return min(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }
};




signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q; cin >> n >> q;

    vector<tuple<int, int, int>> events(n);

    for (int i = 0; i<n; i++) {
        cin >> get<1>(events[i]) >> get<0>(events[i]);
        get<2>(events[i]) = i;    
    }

    sort(events.begin(), events.end());

    vector<pair<int, int>> segtreeRanges;

    for (auto i: events) {
        int l = upper_bound(events.begin(), events.end(), tuple<int, int, int>{get<1>(i)-1, 1e18, 1e18}) - events.begin();
        int r = upper_bound(events.begin(), events.end(), tuple<int, int, int>{get<0>(i), 1e18, 1e18}) - events.begin() - 1;
        segtreeRanges.push_back({l, r});
    }

    for (auto &i: events) swap(get<0>(i), get<1>(i));


    seg tree(n);

    for (int i = 0; i<n; i++) {
        tree.update(1, 0, n-1, i, {get<0>(events[i]), get<2>(events[i])});
    }


    vector<pair<int, int>> parents(n);

    for (int i = 0; i<n; i++) {
        parents[get<2>(events[i])] = tree.query(1, 0, n-1, segtreeRanges[i].first, segtreeRanges[i].second);
    }


    // for (auto i: parents) {
    //     cerr << i.first << " " << i.second << "\n";
    // }


    for (auto &i: events) swap(get<0>(i), get<2>(i));
    sort(events.begin(), events.end());
    for (auto &i: events) swap(get<0>(i), get<2>(i));



    vector<vector<int>> jump(n, vector<int>(20));


    for (int i = 0; i<20; i++) {
        for (int j = 0; j<n; j++) {
            if (i == 0) {jump[j][i] = parents[j].second; continue;}
            jump[j][i] = jump[jump[j][i-1]][i-1];
        }
    }



    for (int i = 0; i<q; i++) {
        int s, e; cin >> s >> e;
        s--;
        e--;

        if (s == e) {cout << 0 << "\n"; continue;}

        int cnt = 1;


        if (get<0>(events[e]) > get<1>(events[s])) {
            for (int i = 19; i>=0; i--) {
                if (get<0>(events[jump[e][i]]) > get<1>(events[s])) {
                    e = jump[e][i];
                    cnt += pow(2, i);
                    cerr << "blub\n";
                }
            }

            e = parents[e].second;
            cnt++;
        }

        if (!(get<0>(events[e]) <= get<1>(events[s]) && get<1>(events[s]) <= get<1>(events[e]))) cout << "impossible\n";
        else cout << cnt << "\n";
    }



    return 0;
}

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