oj.uz

Submission #371012

# Submission time Handle Problem Language Result Execution time Memory
371012 2021-02-25T14:50:09 Z nickmet2004 Railway Trip (JOI17_railway_trip) C++11
100 / 100
 541 ms 16620 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 22 ms 14316 KB Output is correct
3 Correct 25 ms 14316 KB Output is correct
4 Correct 21 ms 14316 KB Output is correct
5 Correct 22 ms 14316 KB Output is correct
6 Correct 22 ms 14444 KB Output is correct
7 Correct 23 ms 14572 KB Output is correct
8 Correct 19 ms 14188 KB Output is correct
9 Correct 23 ms 14572 KB Output is correct
10 Correct 20 ms 14444 KB Output is correct
11 Correct 23 ms 14572 KB Output is correct
12 Correct 22 ms 14572 KB Output is correct
13 Correct 22 ms 14572 KB Output is correct
14 Correct 25 ms 14572 KB Output is correct
15 Correct 23 ms 14572 KB Output is correct
16 Correct 28 ms 14720 KB Output is correct
17 Correct 23 ms 14572 KB Output is correct
18 Correct 23 ms 14720 KB Output is correct
19 Correct 22 ms 14572 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 16188 KB Output is correct
2 Correct 429 ms 15852 KB Output is correct
3 Correct 434 ms 15980 KB Output is correct
4 Correct 436 ms 15980 KB Output is correct
5 Correct 436 ms 16108 KB Output is correct
6 Correct 426 ms 16108 KB Output is correct
7 Correct 423 ms 15980 KB Output is correct
8 Correct 454 ms 15980 KB Output is correct
9 Correct 525 ms 15980 KB Output is correct
10 Correct 526 ms 16108 KB Output is correct
11 Correct 541 ms 16208 KB Output is correct
12 Correct 532 ms 16024 KB Output is correct
13 Correct 529 ms 16068 KB Output is correct
14 Correct 458 ms 16108 KB Output is correct
15 Correct 417 ms 16132 KB Output is correct
16 Correct 417 ms 16108 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 16096 KB Output is correct
2 Correct 356 ms 16236 KB Output is correct
3 Correct 376 ms 15980 KB Output is correct
4 Correct 374 ms 16236 KB Output is correct
5 Correct 534 ms 16164 KB Output is correct
6 Correct 484 ms 16492 KB Output is correct
7 Correct 480 ms 16536 KB Output is correct
8 Correct 485 ms 16236 KB Output is correct
9 Correct 456 ms 16236 KB Output is correct
10 Correct 450 ms 16492 KB Output is correct
11 Correct 450 ms 16492 KB Output is correct
12 Correct 449 ms 16236 KB Output is correct
13 Correct 449 ms 16420 KB Output is correct
14 Correct 451 ms 16364 KB Output is correct
15 Correct 469 ms 16620 KB Output is correct
16 Correct 464 ms 16492 KB Output is correct
17 Correct 436 ms 16392 KB Output is correct
18 Correct 410 ms 16364 KB Output is correct
19 Correct 431 ms 16364 KB Output is correct
20 Correct 395 ms 16236 KB Output is correct
21 Correct 369 ms 16236 KB Output is correct
22 Correct 359 ms 16364 KB Output is correct
23 Correct 353 ms 15980 KB Output is correct