Submission #1299221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299221		random_name	Event Hopping (BOI22_events)	C++20	30 / 100	395 ms	64128 KiB

events

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

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

    Segtree(ll n){
        size = n;
        seg.resize(4*n, LONG_LONG_MAX);
    }

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

        if(l == i && r == i){
            seg[n] = min(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);

        seg[n] = min(seg[2*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 LONG_LONG_MAX;

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

        ll m = (l+r)/2;
        return min(__query(2*n, l, m, left, right), __query(2*n+1, m+1, r, left, right));
    }

    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];
    }

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

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

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

    for(ll i=1;i<20;i++){
        for(ll j=0;j<2*n;j++){
            if(prev[j] != LONG_LONG_MAX)
                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;
        a = A[a].second;
        b = A[b].first;
        while(a < b){
            ll j;
            for(j=0;j<20;j++){
                if(jump[b][j] <= a){
                    j--;
                    break;
                }
            }

            if(j == 20){
                break;
            }

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

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

        if(a >= b){
            cout << cnt << '\n';
        }

        else{
            cout << "impossible\n";
        }
    }
}

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