Submission #1050674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050674		VMaksimoski008	Event Hopping (BOI22_events)	C++17	100 / 100	308 ms	30068 KiB

events

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int maxn = 1e5 + 5;

struct SegTree {
    int n;
    vector<pii> tree;

    SegTree(int _n) : n(_n), tree(4*_n+5, { 1e9, 0 }) {}

    void update(int u, int tl, int tr, int p, int L, int id) {
        if(tl == tr) {
            tree[u] = min(tree[u], { L, id });
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, L, id);
            else update(2*u+1, tm+1, tr, p, L, id);
            tree[u] = min(tree[2*u], tree[2*u+1]);
        }
    }

    pii query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return { 1e9, 0 };
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return min(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }
};

vector<int> graph[maxn], L(maxn), R(maxn);
int up[maxn][20], n, q;

int main() {
    cin >> n >> q;

    vector<array<int, 3> > v(n+1); set<int> s;
    for(int i=1; i<=n; i++) {
        cin >> v[i][1] >> v[i][0]; v[i][2] = i;
        s.insert(v[i][1]); s.insert(v[i][0]);
        L[i] = v[i][1]; R[i] = v[i][0];
    }

    vector<int> comp(s.begin(), s.end());
    for(auto &[r, l, id] : v) {
        if(l == 0 && r == 0) continue;
        l = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
        r = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
    }
    
    SegTree tree(2*n);
    sort(v.begin(), v.end());
    for(auto &[r, l, id] : v) {
        auto [x, y] = tree.query(1, 0, 2*n-1, l, r);
        if(y) up[id][0] = y;
        tree.update(1, 0, 2*n-1, r, l, id);
    }

    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++) up[i][j] = up[up[i][j-1]][j-1];

    while(q--) {
        int a, b;
        cin >> a >> b;

        if(R[a] > R[b]) {
            cout << "impossible\n";
            continue;
        }

        int ans = 0;
        for(int j=19; j>=0; j--)
            if(up[b][j] != 0 && L[up[b][j]] > R[a]) b = up[b][j], ans |= (1 << j);

        if(a == b) cout << ans << '\n';
        else if(L[b] <= R[a]) cout << ans + 1 << '\n';
        else if(up[b][0] && L[up[b][0]] <= R[a]) cout << ans + 2 << '\n';
        else cout << "impossible\n";
    }

    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