Submission #622274

#	Time	Username	Problem	Language	Result	Execution time	Memory
622274		rrrr10000	Event Hopping (BOI22_events)	C++14	100 / 100	521 ms	30372 KiB

events

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
int main(){
    ll n,q;cin>>n>>q;
    vp v;
    vi sx;
    rep(i,n){
        ll a,b;cin>>a>>b;
        v.pb(a,b);
        sx.pb(a);sx.pb(b);
    }
    dupli(sx);
    rep(i,n)v[i].fi=lb(sx,v[i].fi);
    rep(i,n)v[i].se=lb(sx,v[i].se);
    ll N=sx.size();
    vp seg(N*2,P(inf,-1));
    rep(t,n){
        for(ll i=v[t].se+N;i>0;i>>=1)chmin(seg[i],P(v[t].fi,t));
    }
    vvi table(20,vi(n,-1));
    rep(i,n){
        P mi(inf,-1);
        for(ll l=v[i].fi+N,r=v[i].se+1+N;l<r;l>>=1,r>>=1){
            if(l&1)chmin(mi,seg[l++]);
            if(r&1)chmin(mi,seg[--r]);
        }
        if(v[mi.se].fi<v[i].fi)table[0][i]=mi.se;
    }
    rep(i,19)rep(j,n)if(table[i][j]!=-1)table[i+1][j]=table[i][table[i][j]];
    rep(qq,q){
        ll s,t;cin>>s>>t;s--;t--;
        if(s==t){
            out(0);continue;
        }
        ll ans=0;
        for(ll j=19;j>=0;j--)if(table[j][t]!=-1&&v[s].se<v[table[j][t]].fi){
            ans+=1<<j;
            t=table[j][t];
        }
        if(v[t].se<v[s].se)ans=-1;
        else if(v[t].fi>v[s].se){
            if(table[0][t]==-1)ans=-1;
            else ans++;
        }
        if(ans==-1)out("impossible");
        else out(ans+1);
    }
}

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