oj.uz

Submission #1016850

# Submission time Handle Problem Language Result Execution time Memory
1016850 2024-07-08T13:30:22 Z GrindMachine Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 16948 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,l});
    check.push_back({oldl,r});
    check.push_back({oldr,l});
    check.push_back({oldr,r});

    for(auto [x,y] : check){
        if(R[x][0] == r or L[y][0] == x){
            cnt++;
        }
    }
 
    if(arr[oldl] > arr[oldr] and l != y){
        assert(arr[oldl] > arr[l]);

        // cnt = 0;
        // check.clear();
        // 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 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 2396 KB Output is correct
2 Correct 19 ms 16376 KB Output is correct
3 Correct 18 ms 16344 KB Output is correct
4 Correct 17 ms 16472 KB Output is correct
5 Correct 15 ms 16516 KB Output is correct
6 Correct 19 ms 16476 KB Output is correct
7 Correct 26 ms 16476 KB Output is correct
8 Correct 21 ms 16732 KB Output is correct
9 Correct 22 ms 16476 KB Output is correct
10 Correct 25 ms 16780 KB Output is correct
11 Correct 21 ms 16472 KB Output is correct
12 Correct 21 ms 16476 KB Output is correct
13 Correct 28 ms 16476 KB Output is correct
14 Correct 21 ms 16472 KB Output is correct
15 Correct 21 ms 16476 KB Output is correct
16 Correct 21 ms 16472 KB Output is correct
17 Correct 18 ms 16384 KB Output is correct
18 Correct 17 ms 16476 KB Output is correct
19 Correct 13 ms 16352 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16720 KB Output is correct
2 Correct 57 ms 16720 KB Output is correct
3 Correct 59 ms 16540 KB Output is correct
4 Correct 56 ms 16616 KB Output is correct
5 Execution timed out 2082 ms 16948 KB Time limit exceeded
6 Halted 0 ms 0 KB -