Submission #653797

#	Time	Username	Problem	Language	Result	Execution time	Memory
653797		AlperenT	Event Hopping (BOI22_events)	C++17	100 / 100	356 ms	30020 KiB

events

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, K = 20, INF = 1e9 + 5;

int n, q, binlift[N][K], s, e, ans;

struct Event{
    int l, r;

    bool operator < (const Event &sc) const{
        if(r == sc.r) return l < sc.l;
        else return r < sc.r;
    }
};

Event events[N];

vector<pair<Event, int>> vec;

struct SegTree{
    pair<int, int> tree[N * 8];

    SegTree(){
        fill(tree, tree + N * 8, pair{INF, 0});
    }

    void update(int pos, pair<int, int> val, int v = 1, int l = 1, int r = 2 * N - 1){
        if(l == r) tree[v] = min(tree[v], val);
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, val, v * 2, l, m);
            else update(pos, val, v * 2 + 1, m + 1, r);

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

    pair<int, int> query(int l, int r, int v = 1, int tl = 1, int tr = 2 * N - 1){
        if(l > r) return {INF, 0};
        else if(l == tl && r == tr) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            return min(query(l, min(tm, r), v * 2, tl, tm), query(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
        }
    }
};

SegTree sgt;

map<int, int> cmprs;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> events[i].l >> events[i].r;

        cmprs[events[i].l] = cmprs[events[i].r] = 1;
    }

    int tmp = 0;

    for(auto &p : cmprs) p.second = ++tmp;

    for(int i = 1; i <= n; i++){
        events[i].l = cmprs[events[i].l];
        events[i].r = cmprs[events[i].r];

        vec.push_back({events[i], i});
    }

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

    for(auto p : vec){
        Event cur = p.first;

        binlift[p.second][0] = sgt.query(cur.l, cur.r).second;

        sgt.update(cur.r, {cur.l, p.second});
    }

    for(int k = 1; k < K; k++){
        for(int i = 1; i <= n; i++){
            binlift[i][k] = binlift[binlift[i][k - 1]][k - 1];
        }
    }

    while(q--){
        cin >> s >> e;

        ans = 0;

        for(int k = K - 1; k >= 0; k--){
            if(binlift[e][k] != 0 && events[binlift[e][k]].l > events[s].r){
                e = binlift[e][k];
                ans += 1 << k;
            }
        }

        if(s == e) cout << ans << "\n";
        else if(events[s].r >= events[e].l && events[s].r <= events[e].r) cout << ans + 1 << "\n";
        else{
            e = binlift[e][0], ans++;

            if(e == 0) cout << "impossible\n";
            else{
                if(s == e) cout << ans << "\n";
                else if(events[s].r >= events[e].l && events[s].r <= events[e].r) cout << ans + 1 << "\n";
                else cout << "impossible\n";
            }
        }
    }
}

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