Submission #1016304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016304		Aiperiii	Railway Trip 2 (JOI22_ho_t4)	C++14	8 / 100	2093 ms	8532 KiB

Main

#include <bits/stdc++.h>
//#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1e5+5;
int L[N],R[N];
int t_l[N*4],t_r[N*4];

void update_r(int v,int tl,int tr,int l,int r,int x){
    if(r<tl or tr<l)return;
    if(l<=tl && tr<=r){
        t_r[v]=max(t_r[v],x);
        return;
    }
    int tm=(tl+tr)/2;
    update_r(v*2,tl,tm,l,r,x);
    update_r(v*2+1,tm+1,tr,l,r,x);
}
int get_r(int v,int tl,int tr,int pos){
    if(tl==tr)return t_r[v];
    int tm=(tl+tr)/2;
    if(pos<=tm)return max(t_r[v],get_r(v*2,tl,tm,pos));
    else return max(t_r[v],get_r(v*2+1,tm+1,tr,pos));
}
void build(int v,int tl,int tr){
    t_l[v]=1e9;
    if(tl!=tr){
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
    }
}
void update_l(int v,int tl,int tr,int l,int r,int x){
    if(r<tl or tr<l)return;
    if(l<=tl && tr<=r){
        t_l[v]=min(t_l[v],x);
        return;
    }
    int tm=(tl+tr)/2;
    update_l(v*2,tl,tm,l,r,x);
    update_l(v*2+1,tm+1,tr,l,r,x);
}

int get_l(int v,int tl,int tr,int pos){
    if(tl==tr)return t_l[v];
    int tm=(tl+tr)/2;
    if(pos<=tm)return min(t_l[v],get_l(v*2,tl,tm,pos));
    else return min(t_l[v],get_l(v*2+1,tm+1,tr,pos));
}

queue <int> q;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    int m;
    cin>>m;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(a<b){
            update_r(1,1,n,a,min(b-1,a+k-1),b);
        }
        else{
            update_l(1,1,n,max(b+1,a-k+1),a,b);
        }
    }
    for(int i=1;i<=n;i++){
        R[i]=max(i,get_r(1,1,n,i));
        L[i]=min(i,get_l(1,1,n,i));
       
    }
    int Q;
    cin>>Q;
    while(Q--){
        int s,t;
        cin>>s>>t;
        vector <int> d(n+1,-1),vis(n+1);
        d[s]=0;
        q.push(s);
        vis[s]=1;
        set <int> st;
        for(int i=1;i<=n;i++)st.insert(i);
        st.erase(s);
        while(!q.empty()){
            int v=q.front();
            q.pop();
            int mn=1e9,mx=0;
            int mxr=-1,mnl=-1;
            auto it=st.lower_bound(L[v]);
            auto it2=st.upper_bound(R[v]);
            while(it!=it2){
                int i=*it;
                if(d[i]==-1){
                    d[i]=d[v]+1;
                   
                }
                if(L[i]<mn){
                    mn=L[i];
                    mnl=i;
                }
                if(R[i]>mx){
                    mx=R[i];
                    mxr=i;
                }
                it++;
            }
            if(mxr!=-1 && !vis[mxr]){
                vis[mxr]=1;
                st.erase(mxr);
                q.push(mxr);
            }
            if(mnl!=-1 && !vis[mnl]){
                vis[mnl]=1;
                st.erase(mnl);
                q.push(mnl);
            }
        }
        cout<<d[t]<<"\n";
    }
}

/*

*/

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13