Submission #1041859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041859		irmuun	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2075 ms	18188 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k;
    cin>>n>>k;
    int l[n+5],r[n+5];
    iota(l+1,l+n+1,1);
    iota(r+1,r+n+1,1);
    int m;
    cin>>m;
    vector<int>add[n+5],del[n+5];
    int a[m+5],b[m+5];
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        if(a[i]<b[i]){
            add[a[i]].pb(b[i]);
            del[min(a[i]+k-1,b[i]-1)].pb(b[i]);
        }
    }
    multiset<int,greater<int>>st;
    for(int i=1;i<=n;i++){
        for(int j:add[i]){
            st.insert(j);
        }
        if(!st.empty()){
            r[i]=*st.begin();
        }
        for(int j:del[i]){
            st.erase(st.find(j));
        }
        add[i].clear();
        del[i].clear();
    }
    for(int i=1;i<=m;i++){
        if(a[i]>b[i]){
            add[a[i]].pb(b[i]);
            del[max(a[i]-k+1,b[i]+1)].pb(b[i]);
        }
    }
    st.clear();
    multiset<int>st2;
    for(int i=n;i>=1;i--){
        for(int j:add[i]){
            st2.insert(j);
        }
        if(!st2.empty()){
            l[i]=*st2.begin();
        }
        for(int j:del[i]){
            st2.erase(st2.find(j));
        }
    }
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        int ans=-1,cur=0,L=s,R=s;
        vector<int>v;
        v.pb(s);
        while(!v.empty()){
            int Li=L,Ri=R;
            for(int i:v){
                Li=min(Li,l[i]);
                Ri=max(Ri,r[i]);
                if(i==t){
                    ans=cur;
                    break;
                }
            }
            if(ans>-1) break;
            v.clear();
            for(int i=Li;i<L;i++) v.pb(i);
            for(int i=Ri;i>R;i--) v.pb(i);
            L=Li;
            R=Ri;
            cur++;
        }
        cout<<ans<<"\n";
    }
}

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