Submission #1299255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299255		random_name	Event Hopping (BOI22_events)	C++20	100 / 100	433 ms	45336 KiB

events

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

struct Segtree {
    vector<ll> seg;
    vector<ll> A;
    ll size;

    Segtree(ll n, vector<ll> B){
        size = n;
        seg.resize(4*n, -1);
        A = B;
    }

    void __update(ll n, ll l, ll r, ll i, ll val){
        if(l > i || r < i)
            return;

        if(l == i && r == i){
            if(seg[n] == -1 || A[seg[n]] > A[val])
                seg[n] = val;
            return;
        }

        ll m = (l+r)/2;
        __update(2*n, l, m, i, val);
        __update(2*n+1, m+1, r, i, val);

        if(seg[2*n] == -1)
            seg[n] = seg[2*n+1];

        else if(seg[2*n+1] == -1)
            seg[n] = seg[2*n];

        else{
            if(A[seg[2*n]] < A[seg[2*n+1]])
                seg[n] = seg[2*n];

            else
                seg[n] = seg[2*n+1];
        }
    }

    void update(ll i, ll val){
        __update(1, 1, size, i, val);
    }

    ll __query(ll n, ll l, ll r, ll left, ll right){
        if(l > right || r < left)
            return -1;

        if(l >= left && r <= right)
            return seg[n];

        ll m = (l+r)/2;
        ll a = __query(2*n, l, m, left, right);
        ll b = __query(2*n+1, m+1, r, left, right);

        if(a == -1)
            return b;

        if(b == -1)
            return a;

        if(A[a] < A[b])
            return a;
        
        else
            return b;
    }

    ll query(ll left, ll right){
        return __query(1, 1, size, left, right);
    }
};

int main(){
    ll n,q;cin>>n>>q;
    vector<pair<ll, ll>> A(n);
    for(pair<ll, ll> &i:A) cin>>i.first>>i.second;

    vector<ll> compress(2*n);
    for(ll i=0;i<n;i++){
        compress[2*i] = A[i].first;
        compress[2*i+1] = A[i].second;
    }

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

    map<ll, ll> cmprs;
    ll cnt=0;
    for(ll i=0;i<2*n;i++){
        if(i == 2*n-1 || compress[i] != compress[i+1]){
            cmprs[compress[i]] = cnt++;
        }
    }

    for(ll i=0;i<n;i++){
        A[i].first = cmprs[A[i].first];
        A[i].second = cmprs[A[i].second];
    }

    vector<ll> B(n);
    for(ll i=0;i<n;i++)
        B[i] = A[i].first;
    Segtree seg(2*n, B);

    for(ll i=0;i<n;i++){
        seg.update(A[i].second, i);
    }

    vector<ll> prev(n);
    for(ll i=0;i<n;i++){
        prev[i] = seg.query(A[i].first, A[i].second);
    }

    vector<vector<ll>> jump(n, vector<ll>(20));
    for(ll i=0;i<n;i++){
        jump[i][0] = prev[i];
    }

    for(ll i=1;i<20;i++){
        for(ll j=0;j<n;j++){
            jump[j][i] = jump[jump[j][i-1]][i-1];
        }
    }

    while(q--){
        ll a,b;cin>>a>>b;a--,b--;
        if(a == b){
            cout << 0 << '\n';
            continue;
        }

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

        ll cnt=1;
        while(A[a].second < A[b].first){
            ll j;
            for(j=0;j<20;j++){
                if(A[jump[b][j]].first < A[a].second){
                    j--;
                    break;
                }
            }

            if(j == 20)
                break;

            if(j == -1)
                j = 0;

            cnt += 1ll << j;
            b = jump[b][j];
        }

        if(A[a].second < A[b].first){
            cout << "impossible\n";
        }

        else{
            cout << cnt << '\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