Submission #734982

#	Time	Username	Problem	Language	Result	Execution time	Memory
734982		Victor	Event Hopping (BOI22_events)	C++17	45 / 100	469 ms	67496 KiB

events

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

struct Node {
    ll lo,hi,val=INF,id=INF;
    Node *l,*r;

    Node(ll L,ll R) : lo(L),hi(R) {
        if(hi-lo!=1) {
            ll mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);
        }
    }

    pll query(ll L,ll R) {
        if(R<=lo||hi<=L) return {INF,INF};
        if(L<=lo&&hi<=R) return {val,id};
        return min(l->query(L,R),r->query(L,R));
    }

    void update(ll pos,ll x,ll nid) {
        if(pos<lo||hi<=pos) return;
        if(hi-lo==1) {
            if(x<val) {
                val=x;
                id=nid;
            }
            return;
        }

        l->update(pos,x,nid);
        r->update(pos,x,nid);
        tie(val,id)=min(pll(l->val,l->id),pll(r->val,r->id));
    }
};

ll n,q,jmp[20][100005];
vector<pair<pll,ll>> sorted_events;
vpll events;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);


    cin>>n>>q;
    rep(i,0,n+1) jmp[0][i]=n;

    set<ll> coords;
    umap<ll,ll>compress;

    rep(i,0,n) {
        ll s,e;
        cin>>s>>e;
        events.emplace_back(s,e);
        coords.insert(s);
        coords.insert(e);
    }

    {
        ll cnt=0;
        trav(val,coords) compress[val]=cnt++;
        rep(i,0,n) {
            events[i].first=compress[events[i].first];
            events[i].second=compress[events[i].second];
            sorted_events.emplace_back(events[i],i);
        }
    }

    sort(all(sorted_events));
    Node segtree(0,2*n+1);

    trav(event,sorted_events) {
        ll s,e,id=event.second;
        tie(s,e)=event.first;

        pll best=segtree.query(s,e+1);
        if(best.first!=INF) jmp[0][id]=best.second;
        segtree.update(e,s,id);
    }

    rep(j,1,20) rep(i,0,n+1) jmp[j][i]=jmp[j-1][jmp[j-1][i]]; 

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

        if(events[a].second>events[b].second) {
            cout<<"impossible"<<endl;
            continue;

        } else if(a==b) {
            cout<<0<<endl;
            continue;
        }

        ll ans=0;

        per(j,0,20) {
            ll nxt=jmp[j][b];
            if(nxt==n||events[nxt].first<=events[a].second) continue;
            b=nxt;
            ans+=1<<j;
        }

        ll nxt=jmp[0][b];
        if(nxt==n) {
            cout<<"impossible"<<endl;
            continue;
        }

        // cout<<"a = "<<events[a].first<<' '<<events[a].second<<endl;
        // cout<<"b = "<<events[nxt].first<<' '<<events[nxt].second<<endl;
        ++ans;
        if(events[a].second<events[b].first) ++ans;
        cout<<ans<<endl;
    }

    _Exit(0);
    return 0;
}

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