oj.uz

Submission #339215

# Submission time Handle Problem Language Result Execution time Memory
339215 2020-12-24T20:52:38 Z couplefire Railway Trip (JOI17_railway_trip) C++17
0 / 100
 735 ms 17004 KB 
#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) 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 << lo2+lo1-1 << endl;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 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 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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