oj.uz

Submission #1015970

# Submission time Handle Problem Language Result Execution time Memory
1015970 2024-07-07T07:19:18 Z GrindMachine Railway Trip (JOI17_railway_trip) C++17
0 / 100
 2000 ms 16720 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{
            l2 = L[r][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
0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 21 ms 16476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16720 KB Output is correct
2 Incorrect 57 ms 16668 KB Output isn't correct
3 Halted 0 ms 0 KB -