Submission #339229

#	Time	Username	Problem	Language	Result	Execution time	Memory
339229		couplefire	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	1371 ms	17900 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXLOG 18

int n, k, q;
int level[MAXN];
int highRight[MAXN][MAXLOG];
int highLeft[MAXN][MAXLOG];

void initRight(){
    stack<pair<int, int>> st;
    for(int i = n; i>=1; i--){
        while(!st.empty() && st.top().first < level[i]) st.pop();
        if(!st.empty()) highRight[i][0] = st.top().second;
        else highRight[i][0] = i;
        st.push({level[i], i});
    }
}

void initLeft(){
    stack<pair<int, int>> st;
    for(int i = 1; i<=n; i++){
        while(!st.empty() && st.top().first < level[i]) st.pop();
        if(!st.empty()) highLeft[i][0] = st.top().second;
        else highLeft[i][0] = i;
        st.push({level[i], i});
    }
}

pair<int, int> lift(int b, int mid){
    int curLeft = b, curRight = b;
    for(int i = MAXLOG-1; i>=0; i--){
        if(mid&(1<<i)){
            int pLeft = curLeft, pRight = curRight;
            curLeft = min(highLeft[pLeft][i], highLeft[pRight][i]);
            curRight = max(highRight[pLeft][i], highRight[pRight][i]);
        }
    }
    return {curLeft, curRight};
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> q;
    for(int i = 0; i<n; i++) cin >> level[i+1];
    initRight(); initLeft();
    for(int lvl = 1; lvl<MAXLOG; lvl++){
        for(int i = 1; i<=n; i++){
            highRight[i][lvl] = max(highRight[highLeft[i][lvl-1]][lvl-1], highRight[highRight[i][lvl-1]][lvl-1]);
            highLeft[i][lvl] = min(highLeft[highLeft[i][lvl-1]][lvl-1], highLeft[highRight[i][lvl-1]][lvl-1]);
        }
    }
    // cout << highRight[2][1] << endl;
    while(q--){
        int a, b; cin >> a >> b;
        if(a > b) swap(a, b);
        int lo1 = 0, hi1 = MAXN;
        int pos;
        while(lo1 < hi1){
            int mid = lo1+(hi1-lo1)/2;
            auto p = lift(a, mid);
            if(highRight[p.second][0] >= b || highRight[p.first][0] >= b) hi1 = mid, pos = p.second;
            else lo1 = mid+1;
        }
        int lo2 = 0, hi2 = MAXN;
        while(lo2 < hi2){
            int mid = lo2+(hi2-lo2)/2;
            auto p = lift(b, mid);
            if(p.first <= pos) hi2 = mid;
            else lo2 = mid+1;
        }
        // cout << lo1 << " " << lo2 << endl;
        cout << lo1 + lo2 - 1 << endl;
    }
}

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