oj.uz

답안 #339229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339229 2020-12-24T21:19:32 Z couplefire Railway Trip (JOI17_railway_trip) C++17
100 / 100
 1371 ms 17900 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 || 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 48 ms 15172 KB Output is correct
3 Correct 44 ms 15176 KB Output is correct
4 Correct 42 ms 15084 KB Output is correct
5 Correct 42 ms 15212 KB Output is correct
6 Correct 41 ms 15212 KB Output is correct
7 Correct 44 ms 15700 KB Output is correct
8 Correct 39 ms 15852 KB Output is correct
9 Correct 45 ms 15852 KB Output is correct
10 Correct 45 ms 15852 KB Output is correct
11 Correct 51 ms 15724 KB Output is correct
12 Correct 55 ms 15872 KB Output is correct
13 Correct 51 ms 15724 KB Output is correct
14 Correct 52 ms 15724 KB Output is correct
15 Correct 51 ms 15724 KB Output is correct
16 Correct 52 ms 15724 KB Output is correct
17 Correct 43 ms 15468 KB Output is correct
18 Correct 42 ms 15468 KB Output is correct
19 Correct 41 ms 15468 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 770 ms 15488 KB Output is correct
2 Correct 791 ms 16876 KB Output is correct
3 Correct 739 ms 16876 KB Output is correct
4 Correct 720 ms 17004 KB Output is correct
5 Correct 723 ms 16748 KB Output is correct
6 Correct 703 ms 16708 KB Output is correct
7 Correct 718 ms 17000 KB Output is correct
8 Correct 1359 ms 16972 KB Output is correct
9 Correct 1351 ms 17788 KB Output is correct
10 Correct 1359 ms 17900 KB Output is correct
11 Correct 1355 ms 17588 KB Output is correct
12 Correct 1361 ms 17836 KB Output is correct
13 Correct 1364 ms 17772 KB Output is correct
14 Correct 883 ms 17088 KB Output is correct
15 Correct 647 ms 16748 KB Output is correct
16 Correct 596 ms 16876 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 15084 KB Output is correct
2 Correct 482 ms 16876 KB Output is correct
3 Correct 474 ms 16756 KB Output is correct
4 Correct 482 ms 16876 KB Output is correct
5 Correct 1371 ms 17588 KB Output is correct
6 Correct 1231 ms 17524 KB Output is correct
7 Correct 1216 ms 17772 KB Output is correct
8 Correct 1237 ms 17516 KB Output is correct
9 Correct 945 ms 17388 KB Output is correct
10 Correct 940 ms 17516 KB Output is correct
11 Correct 912 ms 17388 KB Output is correct
12 Correct 955 ms 17516 KB Output is correct
13 Correct 954 ms 17644 KB Output is correct
14 Correct 1147 ms 17388 KB Output is correct
15 Correct 1191 ms 17388 KB Output is correct
16 Correct 1212 ms 17400 KB Output is correct
17 Correct 845 ms 17512 KB Output is correct
18 Correct 879 ms 17516 KB Output is correct
19 Correct 859 ms 17328 KB Output is correct
20 Correct 580 ms 17064 KB Output is correct
21 Correct 477 ms 16876 KB Output is correct
22 Correct 467 ms 16876 KB Output is correct
23 Correct 469 ms 16876 KB Output is correct