Submission #1050794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050794		Ahmed57	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	198 ms	19028 KiB

railway_trip

#include "bits/stdc++.h"
using namespace std;
int L[100001][20];
int R[100001][20];
int main(){
    int n,k,q;
    cin>>n>>k>>q;
    int arr[n+1];
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
    }
    stack<int> st;
    for(int i = 1;i<=n;i++){
        while(!st.empty()&&arr[st.top()]<arr[i])st.pop();
        if(!st.empty()){
            L[i][0] = st.top();
        }else L[i][0] = i;
        st.push(i);
    }
    while(!st.empty())st.pop();
    for(int i = n;i>=1;i--){
        while(!st.empty()&&arr[st.top()]<arr[i])st.pop();
        if(!st.empty()){
            R[i][0] = st.top();
        }else R[i][0] = i;
        st.push(i);
    }
    for(int j = 1;j<20;j++){
        for(int i = 1;i<=n;i++){
            L[i][j] = min(L[L[i][j-1]][j-1],L[R[i][j-1]][j-1]);
            R[i][j] = max(R[R[i][j-1]][j-1],R[L[i][j-1]][j-1]);
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        int l = min(a,b) , r = min(a,b);
        int ans = 0;
        for(int i = 19;i>=0;i--){
            if(max(R[l][i],R[r][i])<max(a,b)){
                int A = min(L[l][i],L[r][i]);
                int B = max(R[l][i],R[r][i]);
                l = A;r = B;
                ans+=(1<<i);
            }
        }
        int c = r;
        l = max(a,b);
        r = max(a,b);
        for(int i = 19;i>=0;i--){
            if(min(L[l][i],L[r][i])>c){
                int A = min(L[l][i],L[r][i]);
                int B = max(R[l][i],R[r][i]);
                l = A;r = B;
                ans+=(1<<i);
            }
        }
        cout<<ans<<endl;
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55