제출 #1266590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266590		warrenn	Event Hopping (BOI22_events)	C++20	20 / 100	305 ms	34276 KiB

events

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

const int maxn=1e5;
int n,qu;
int s[maxn+2],e[maxn+2];
map<int,int>conv;
vector<pair<int,int> >st;
pair<int,int>hmm[maxn+2];

pair<int,int>merg(pair<int,int>a,pair<int,int> b){
    if(a<b)return a;
    return b;
}

void build(int idx,int l,int r){
    if(l==r){
        st[idx]=hmm[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*idx,l,mid);
    build(2*idx+1,mid+1,r);
    st[idx]=merg(st[2*idx],st[2*idx+1]);
}

pair<int,int> query(int idx,int l,int r,int posl,int posr){
    if(l>posr || r<posl)return {1e18,0};
    if(l>=posl && r<=posr)return st[idx];
    int mid=(l+r)/2;
    return merg(query(2*idx,l,mid,posl,posr),query(2*idx+1,mid+1,r,posl,posr));
}

signed main(){
    cin>>n>>qu;
    st=vector<pair<int,int> >(4*n+1);

    vector<int>res;
    for(int q=1;q<=n;q++){
        cin>>s[q]>>e[q];
        res.push_back(e[q]);
        hmm[q]={1e18,0};
    }
    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    int cnt=1;
    for(int q=0;q<res.size();q++){
        if(q==0 || res[q]!=res[q-1]){
            conv[res[q]]=cnt;
            cnt++;
        }
    }
    for(int q=1;q<=n;q++){
        int hah=conv[e[q]];
        if(hmm[hah].first>s[q]){
            hmm[hah]={s[q],q};
        }
    }
    build(1,1,n);
    int bin[n+2][21];

    for(int q=1;q<=n;q++){
        int l=0;
        int r=res.size()-1;
        int awal=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(res[mid]>=s[q]){
                awal=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
            
        }
        //assert(conv[e[q]]-awal<=2);
        bin[q][0]=query(1,1,n,awal+1,conv[e[q]]).second;
    }
    for(int lvl=1;lvl<=20;lvl++){
        for(int idx=1;idx<=n;idx++){
            bin[idx][lvl]=bin[bin[idx][lvl-1]][lvl-1];
        }
    }
    while(qu--){
        int u,v;
        cin>>u>>v;
        if(u==v){
            cout<<0<<endl;
            continue;
        }
        if(e[v]<e[u]){
            cout<<"impossible"<<endl;
            continue;
        }
        if(s[v]>=s[u] && s[v]<=e[u]){
            cout<<1<<endl;
            continue;
        }
        int ans=0;
        int ada=0;
        for(int lvl=20;lvl>=0;lvl--){
            if(s[bin[v][lvl]]>e[u]){
                ans+=(1<<lvl);
                v=bin[v][lvl];
            }
            else{
                ada=1;
            }
        }
        if(ada==0){
            cout<<"impossible"<<endl;
            continue;
        }
        cout<<ans+2<<endl;
    }
}

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