Submission #948604

#	Time	Username	Problem	Language	Result	Execution time	Memory
948604		Hugo1729	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	124 ms	16916 KiB

railway_trip

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

const int MAXN=100000, MAXL=17;

int mleft[MAXN][MAXL], mright[MAXN][MAXL];

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n,k,q; cin >> n >> k >> q;
    vector<int> stations(n);
    for(int i=0;i<n;i++)cin >> stations[i];

    stack<pair<int,int>> monotonic1,monotonic2;

    for(int i=0;i<n;i++){
        while(monotonic1.size()>0&&monotonic1.top().first<stations[i]){
            monotonic1.pop();
        }
        if(monotonic1.empty()){
            mleft[i][0]=i;
        } else{
            mleft[i][0]=monotonic1.top().second;
        }
        monotonic1.push({stations[i],i});
    }

    for(int i=n-1;i>=0;i--){
        while(monotonic2.size()>0&&monotonic2.top().first<stations[i]){
            monotonic2.pop();
        }
        if(monotonic2.empty()){
            mright[i][0]=i;
        } else{
            mright[i][0]=monotonic2.top().second;
        }
        // cout << i << ' ' << mleft[i][0] << ' ' << mright[i][0] << '\n';
        monotonic2.push({stations[i],i});
    }

    for(int j=1;j<MAXL;j++){
        for(int i=0;i<n;i++){
            mleft[i][j]=min(mleft[mleft[i][j-1]][j-1],mleft[mright[i][j-1]][j-1]);
            mright[i][j]=max(mright[mright[i][j-1]][j-1],mright[mleft[i][j-1]][j-1]);
        }
    }

    while(q--){
        int a,b; cin >> a >> b;a--;b--;
        if(a>b)swap(a,b);

        int ans=0,l=a,r=a;

        for(int j=MAXL-1;j>=0;j--){
            int nl=min(mleft[l][j],mleft[r][j]),nr=max(mright[l][j],mright[r][j]);
            if(nr<b){
                l=nl;r=nr;
                ans+=(1<<j);
                // cout << "a " << j << ' ' << l << ' ' << r << '\n';
            }
        }

        a=r;
        l=b;
        r=b;

        for(int j=MAXL-1;j>=0;j--){
            int nl=min(mleft[l][j],mleft[r][j]),nr=max(mright[l][j],mright[r][j]);
            if(nl>a){
                l=nl;r=nr;
                ans+=(1<<j);
                // cout << "b " << j << ' ' << l << ' ' << r << '\n';
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

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