Submission #857698

#	Time	Username	Problem	Language	Result	Execution time	Memory
857698		vgtcross	Event Hopping (BOI22_events)	C++17	100 / 100	206 ms	27728 KiB

events

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 100100;
const int K = 18;

int jmp[K][N];

struct segtree {
    pii v;
    int l, r, m;
    segtree *lc = nullptr, *rc = nullptr;
    
    segtree(int L, int R, vector<int> &u){
        l = L;
        r = R;
        m = (l + r) / 2;
        if (l == r) {
            v = {u[m], m};
            return;
        }
        
        lc = new segtree(l, m, u);
        rc = new segtree(m+1, r, u);
        v = min(lc->v, rc->v);
    }
    
    pii range_min(int L, int R) {
        if (L > R) return {2e9, 2e9};
        if (l == L && r == R) return v;
        return min(lc->range_min(L, min(R, m)), rc->range_min(max(m+1, L), R));
    }
    
    void del() {
        if (lc != nullptr) lc->del();
        if (rc != nullptr) rc->del();
        delete lc;
        delete rc;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    
    vector<array<int, 3>> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i][1] >> v[i][0];
        v[i][2] = i+1;
    }
    sort(v.begin(), v.end());
    
    vector<int> pos(n+1);
    vector<int> d(n);
    set<pii> st;
    for (int i = 0; i < n; ++i) {
        st.insert({v[i][0], i});
        pii b = *st.lower_bound({v[i][1], -1});
        d[i] = b.second;
        pos[v[i][2]] = i;
    }
    
    segtree seg(0, n-1, d);
    for (int i = 0; i < n; ++i) {
        jmp[0][i] = seg.range_min(d[i], i).second;
    }
    
    for (int i = 1; i < K; ++i) {
        for (int j = 0; j < n; ++j) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
    }
    
    while (q--) {
        int a, b;
        cin >> a >> b;
        a = pos[a];
        b = pos[b];
        
        if (v[a][0] > v[b][0]) {
            cout << "impossible\n";
            continue;
        } else if (a == b) {
            cout << "0\n";
            continue;
        } else if (d[b] <= a) {
            cout << "1\n";
            continue;
        }
        
        int ans = 0;
        for (int i = K-1; i >= 0; --i) {
            if (a < d[jmp[i][b]]) {
                b = jmp[i][b];
                ans += 1 << i;
            }
        }
        
        b = jmp[0][b];
        
        if (a < d[b]) cout << "impossible\n";
        else cout << ans+2 << '\n';
        cout << flush;
    }
    
    seg.del();
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

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