oj.uz

Submission #1015969

# Submission time Handle Problem Language Result Execution time Memory
1015969 2024-07-07T07:18:52 Z GrindMachine Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 18260 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 604 KB Output is correct
2 Correct 27 ms 16604 KB Output is correct
3 Correct 23 ms 16780 KB Output is correct
4 Correct 19 ms 16732 KB Output is correct
5 Correct 18 ms 16728 KB Output is correct
6 Correct 19 ms 16732 KB Output is correct
7 Correct 22 ms 16956 KB Output is correct
8 Correct 30 ms 17060 KB Output is correct
9 Correct 31 ms 17240 KB Output is correct
10 Correct 28 ms 16988 KB Output is correct
11 Correct 29 ms 17236 KB Output is correct
12 Correct 27 ms 17240 KB Output is correct
13 Correct 28 ms 16988 KB Output is correct
14 Correct 26 ms 17248 KB Output is correct
15 Correct 28 ms 17244 KB Output is correct
16 Correct 27 ms 16988 KB Output is correct
17 Correct 22 ms 16984 KB Output is correct
18 Correct 19 ms 16984 KB Output is correct
19 Correct 18 ms 16988 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 17492 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 18256 KB Output is correct
2 Correct 68 ms 18256 KB Output is correct
3 Correct 65 ms 18260 KB Output is correct
4 Correct 62 ms 18256 KB Output is correct
5 Execution timed out 2041 ms 17452 KB Time limit exceeded
6 Halted 0 ms 0 KB -