oj.uz

Submission #1016826

# Submission time Handle Problem Language Result Execution time Memory
1016826 2024-07-08T13:01:38 Z GrindMachine Railway Trip (JOI17_railway_trip) C++17
0 / 100
 33 ms 33112 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;
 
    while(true){
        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++;
    }
    
    int oldl = l, oldr = r;
    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++;
    }
    
    int cnt = 0;
    
    vector<pair<int,int>> check;
    check.push_back({oldl,r});
    check.push_back({oldr,l});

    for(auto [x,y] : check){
        if(R[x][0] == r or L[y][0] == x){
            cnt++;
        }
    }
 
    assert(cnt);
    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 Runtime error 2 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4956 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 33068 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 33112 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -