oj.uz

Submission #948611

# Submission time Handle Problem Language Result Execution time Memory
948611 2024-03-18T08:42:20 Z Hugo1729 Railway Trip (JOI17_railway_trip) C++11
0 / 100
 74 ms 14500 KB 
#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';z
            }
        }

        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 14500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 14416 KB Output isn't correct
2 Halted 0 ms 0 KB -