Submission #371012

#	Time	Username	Problem	Language	Result	Execution time	Memory
371012		nickmet2004	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	541 ms	16620 KiB

railway_trip

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n , k , q , a[N];
int L[17][N] , R[17][N];
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> q;
    for(int i = 1; i <= n; ++i)cin >> a[i];
    for(int i = n; i; --i){
        R[0][i] = i + 1;
        while(R[0][i] <= n && a[R[0][i]] < a[i]) R[0][i] = R[0][R[0][i]];
    }
    for(int i = 1; i <= n; ++i){
        L[0][i] = i - 1;
        while(L[0][i] && a[L[0][i]] < a[i]) L[0][i] = L[0][L[0][i]];
    }
    L[0][1]= 1; R[0][n] = n;
    for(int i = 1; i < 17; ++i){
        for(int j= 1; j<= n; ++j){
            L[i][j] = min(L[i - 1][L[i - 1][j]] , L[i - 1][R[i - 1][j]]);
            R[i][j] = max(R[i - 1][R[i - 1][j]] , R[i - 1][L[i - 1][j]]);
        }
    }
    while(q--){
        int a , b;
        cin >> a >> b;
        if(a>b)swap(a,b);
        int l = a , r= a , ans = 0 ,c;
        for(int i = 16; ~i; --i){
            if(max(R[i][l] , R[i][r]) < b){
                int x = l , y = r;
                l= min(L[i][x] , L[i][y]); r=max(R[i][x] , R[i][y]);
                ans += 1 << i;
            }
        }
        c = r;
        l = b , r = b;
        for(int i = 16; ~i; --i){
            if(min(L[i][l] , L[i][r]) > c){
                int x = l , y = r;
                l= min(L[i][x] , L[i][y]); r=max(R[i][x] , R[i][y]);
                ans += 1 << i;
            }
        }
        cout << ans << endl;
    }
return 0;
}

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