oj.uz

Submission #1015971

# Submission time Handle Problem Language Result Execution time Memory
1015971 2024-07-07T07:19:58 Z GrindMachine Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 18276 KB 
#include <bits/stdc++.h>
 
using namespace std ;

// modified from: https://oj.uz/submission/825591

const int MAX = 1e5 + 10 ;
 
int arr[MAX] ;
int n , k , q ;
 
int L[MAX][20] , R[MAX][20] ;
 
int solve(int x , int y)
{
    int ans = 0;
    int l = x, r = x;
    int iter = 10;

    while(true){
        // cout << l << " " << r << endl;
        int l2 = -1, r2 = -1;
        if(arr[l] > arr[r]){
            l2 = L[l][0], r2 = R[l][0];
        }
        else if(arr[l] < arr[r]){
            l2 = L[r][0], r2 = R[r][0];
        }
        else{
            l2 = L[l][0], r2 = R[r][0];
        }

        // int l2 = min(L[l][0],L[r][0]);
        // int r2 = max(R[l][0],R[r][0]);
        if(r2 >= y) break;
        l = l2, r = r2;
        ans++;
    }
    
    x = r;
    l = r = y;

    while(true){
        int l2 = min(L[l][0],L[r][0]);
        int r2 = max(R[l][0],R[r][0]);
        if(l2 <= x) break;
        l = l2, r = r2;
        ans++;
    }

    return ans;

    // int ans = 0 ;
    // int l = x , r = x ;
    // for(int i = 19 ; i >= 0 ; --i)
    // {
    //     if(max(R[l][i] , R[r][i]) < y)
    //     {
    //         ans += (1 << i)  ;
    //         int l2 = l , r2 = r ;
    //         l = min(L[l2][i] , L[r2][i]) ;
    //         r = max(R[l2][i] , R[r2][i]) ;
    //     }
    // }
    // x = r ;
    // l = r = y ;
    // for(int i = 19 ; i >= 0 ; --i)
    // {
    //     if(min(L[l][i] , L[r][i]) > x)
    //     {
    //         ans += (1 << i) ;
    //         int l2 = l , r2 = r ;
    //         l = min(L[l2][i] , L[r2][i]) ;
    //         r = max(R[l2][i] , R[r2][i]) ;
    //     }
    // }
    // return ans ;
}
 
int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cin>>n>>k>>q ;
    for(int i = 1 ; i <= n ; ++i)
        cin>>arr[i] ;
    stack<int>s ;
    for(int i = 1 ; i <= n ; ++i)
    {
        L[i][0] = 1 ;
        while(s.size() && arr[i] > arr[s.top()])
            s.pop() ;
        if(s.size())
            L[i][0] = s.top() ;
        s.push(i) ;
    }
    while(s.size())
        s.pop() ;
    for(int i = n ; i >= 1 ; --i)
    {
        R[i][0] = n ;
        while(s.size() && arr[i] > arr[s.top()])
            s.pop() ;
        if(s.size())
            R[i][0] = s.top() ;
        s.push(i) ;
    }
    for(int j = 1 ; j < 20 ; ++j)
    {
        for(int i = 1 ; i <= n ; ++i)
        {
            // int x = L[i][j-1], y = R[i][j-1];
            // if(arr[x] < arr[y]) swap(x,y);
            // if(arr[x] >= arr[y]){
            //     L[i][j] = L[x][j-1];
            //     R[i][j] = R[x][j-1];
            // }
            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 x , y ;
        cin>>x>>y ;
        if(x > y)
            swap(x , y) ;
        cout<<solve(x , y)<<"\n" ;
    }
    return 0 ;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 22 ms 16732 KB Output is correct
3 Correct 21 ms 16732 KB Output is correct
4 Correct 21 ms 16728 KB Output is correct
5 Correct 25 ms 16732 KB Output is correct
6 Correct 21 ms 16728 KB Output is correct
7 Correct 28 ms 17120 KB Output is correct
8 Correct 25 ms 16988 KB Output is correct
9 Correct 29 ms 16988 KB Output is correct
10 Correct 27 ms 17180 KB Output is correct
11 Correct 28 ms 16984 KB Output is correct
12 Correct 26 ms 16988 KB Output is correct
13 Correct 25 ms 16988 KB Output is correct
14 Correct 27 ms 16988 KB Output is correct
15 Correct 26 ms 16972 KB Output is correct
16 Correct 26 ms 16988 KB Output is correct
17 Correct 21 ms 16984 KB Output is correct
18 Correct 20 ms 17016 KB Output is correct
19 Correct 18 ms 16984 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 17364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 18252 KB Output is correct
2 Correct 63 ms 18276 KB Output is correct
3 Correct 65 ms 18064 KB Output is correct
4 Correct 60 ms 18260 KB Output is correct
5 Execution timed out 2078 ms 17492 KB Time limit exceeded
6 Halted 0 ms 0 KB -