Submission #1333204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333204		Luvidi	Railway Trip 2 (JOI22_ho_t4)	C++20	25 / 100	59 ms	22984 KiB

Main

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

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n,k;
    cin>>n>>k;
    int m;
    cin>>m;
    pii a[m];
    for(int i=0;i<m;i++)cin>>a[i].fs>>a[i].sc;
    vector<int> v[n+1];
    for(auto[x,y]:a)v[x].pb(y);
    int bl[20][n+1],br[20][n+1];
    for(int i=1,m=0;i<=n;i++){
        m=max(m,i);
        for(int y:v[i])m=max(m,y);
        br[0][i]=m;
    }
    for(int i=n,m=n;i;i--){
        m=min(m,i);
        for(int y:v[i])m=min(m,y);
        bl[0][i]=m;
    }
    for(int t=1;t<20;t++){
        for(int i=1;i<=n;i++){
            br[t][i]=br[t-1][br[t-1][i]];
            bl[t][i]=bl[t-1][bl[t-1][i]];
        }
    }
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        int ans=1;
        if(s<t){
            for(int z=19;z>-1;z--){
                if(br[z][s]<t){
                    ans+=1<<z;
                    s=br[z][s];
                }
            }
            s=br[0][s];
            if(s<t)ans=-1;
        }else{
            for(int z=19;z>-1;z--){
                if(bl[z][s]>t){
                    ans+=1<<z;
                    s=bl[z][s];
                }
            }
            s=bl[0][s];
            if(s>t)ans=-1;
        }
        cout<<ans<<'\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}

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