Submission #1189628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189628		user149	Event Hopping (BOI22_events)	C++20	0 / 100	1602 ms	217796 KiB

events

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

using pii=pair<int,int>;

struct st{
    int l,r;
    pii val={-1,-1}; // {e,node}

    st* left=0;
    st* right=0;
    st(int L,int R){
        l=L;
        r=R;
    }

    void create(){
        if(l==r || left!=0) return;
        int mid=(l+r)/2;
        left=new st(l,mid);
        right=new st(mid+1,r);
    }

    void update(int i,pii v){
        create();
        if(l>i || r<i) return;
        if(l==r){
            val=max(val,v);
            return;
        }
        left->update(i,v);
        right->update(i,v);
        val=max(left->val,right->val);
    };

    pii query(int a,int b){
        create();
        if(l>b || r<a) return {-1,-1};
        if(a<=l && r<=b) return val;
        return max(left->query(a,b),right->query(a,b));
    }
};

int s[100005];
int e[100005];

st segtree(0,1e9+5);

int par[100005];

int main(){
    int N,Q;
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        cin>>s[i]>>e[i];
        segtree.update(s[i],{e[i],i});
    }
    for(int i=1;i<=N;i++){
        auto [end,node]=segtree.query(0,e[i]);
        if(end>e[i]) par[i]=node;
        else par[i]=-1;
    }
    for(int i=1;i<=Q;i++){
        int a,b;
        cin>>a>>b;
        if(a==b){
            cout<<"0\n";
            continue;
        }
        
        int ans=0;
        while(par[a]!=-1 && e[par[a]]<e[b]){
            a=par[a];
            ans++;
        }

        if(s[b]<=e[a] && e[a]<=e[b]){
            cout<<ans+1<<'\n';
        }
        else if(par[a]!=1){
            a=par[a];
            ans++;
            if(s[b]<=e[a] && e[a]<=e[b]){
                cout<<ans+1<<'\n';
            }
            else cout<<"impossible\n";
        }
        else cout<<"impossible\n";
    }
}

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