oj.uz

Submission #1050794

# Submission time Handle Problem Language Result Execution time Memory
1050794 2024-08-09T14:35:43 Z Ahmed57 Railway Trip (JOI17_railway_trip) C++17
100 / 100
 198 ms 19028 KB 
#include "bits/stdc++.h"
using namespace std;
int L[100001][20];
int R[100001][20];
int main(){
    int n,k,q;
    cin>>n>>k>>q;
    int arr[n+1];
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
    }
    stack<int> st;
    for(int i = 1;i<=n;i++){
        while(!st.empty()&&arr[st.top()]<arr[i])st.pop();
        if(!st.empty()){
            L[i][0] = st.top();
        }else L[i][0] = i;
        st.push(i);
    }
    while(!st.empty())st.pop();
    for(int i = n;i>=1;i--){
        while(!st.empty()&&arr[st.top()]<arr[i])st.pop();
        if(!st.empty()){
            R[i][0] = st.top();
        }else R[i][0] = i;
        st.push(i);
    }
    for(int j = 1;j<20;j++){
        for(int i = 1;i<=n;i++){
            L[i][j] = min(L[L[i][j-1]][j-1],L[R[i][j-1]][j-1]);
            R[i][j] = max(R[R[i][j-1]][j-1],R[L[i][j-1]][j-1]);
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        int l = min(a,b) , r = min(a,b);
        int ans = 0;
        for(int i = 19;i>=0;i--){
            if(max(R[l][i],R[r][i])<max(a,b)){
                int A = min(L[l][i],L[r][i]);
                int B = max(R[l][i],R[r][i]);
                l = A;r = B;
                ans+=(1<<i);
            }
        }
        int c = r;
        l = max(a,b);
        r = max(a,b);
        for(int i = 19;i>=0;i--){
            if(min(L[l][i],L[r][i])>c){
                int A = min(L[l][i],L[r][i]);
                int B = max(R[l][i],R[r][i]);
                l = A;r = B;
                ans+=(1<<i);
            }
        }
        cout<<ans<<endl;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 16 ms 16728 KB Output is correct
3 Correct 17 ms 16732 KB Output is correct
4 Correct 16 ms 16556 KB Output is correct
5 Correct 16 ms 16580 KB Output is correct
6 Correct 18 ms 16732 KB Output is correct
7 Correct 22 ms 16984 KB Output is correct
8 Correct 17 ms 17032 KB Output is correct
9 Correct 25 ms 17244 KB Output is correct
10 Correct 21 ms 16988 KB Output is correct
11 Correct 25 ms 17028 KB Output is correct
12 Correct 23 ms 16984 KB Output is correct
13 Correct 22 ms 16988 KB Output is correct
14 Correct 23 ms 16988 KB Output is correct
15 Correct 29 ms 17020 KB Output is correct
16 Correct 22 ms 16988 KB Output is correct
17 Correct 21 ms 16936 KB Output is correct
18 Correct 22 ms 17040 KB Output is correct
19 Correct 21 ms 16984 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 18256 KB Output is correct
2 Correct 155 ms 18328 KB Output is correct
3 Correct 148 ms 18224 KB Output is correct
4 Correct 148 ms 18336 KB Output is correct
5 Correct 150 ms 18256 KB Output is correct
6 Correct 147 ms 18328 KB Output is correct
7 Correct 146 ms 18308 KB Output is correct
8 Correct 157 ms 18352 KB Output is correct
9 Correct 178 ms 18676 KB Output is correct
10 Correct 163 ms 18720 KB Output is correct
11 Correct 184 ms 18716 KB Output is correct
12 Correct 169 ms 18972 KB Output is correct
13 Correct 159 ms 18724 KB Output is correct
14 Correct 159 ms 18260 KB Output is correct
15 Correct 160 ms 18256 KB Output is correct
16 Correct 145 ms 18012 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 18256 KB Output is correct
2 Correct 146 ms 18280 KB Output is correct
3 Correct 143 ms 18260 KB Output is correct
4 Correct 162 ms 18260 KB Output is correct
5 Correct 160 ms 18668 KB Output is correct
6 Correct 177 ms 18788 KB Output is correct
7 Correct 162 ms 18768 KB Output is correct
8 Correct 164 ms 18768 KB Output is correct
9 Correct 170 ms 18768 KB Output is correct
10 Correct 157 ms 18840 KB Output is correct
11 Correct 162 ms 18772 KB Output is correct
12 Correct 163 ms 19028 KB Output is correct
13 Correct 156 ms 18776 KB Output is correct
14 Correct 167 ms 18768 KB Output is correct
15 Correct 168 ms 18652 KB Output is correct
16 Correct 167 ms 18768 KB Output is correct
17 Correct 175 ms 18772 KB Output is correct
18 Correct 198 ms 18592 KB Output is correct
19 Correct 189 ms 19000 KB Output is correct
20 Correct 195 ms 18468 KB Output is correct
21 Correct 154 ms 18260 KB Output is correct
22 Correct 167 ms 18264 KB Output is correct
23 Correct 180 ms 18260 KB Output is correct