oj.uz

Submission #825591

# Submission time Handle Problem Language Result Execution time Memory
825591 2023-08-15T05:27:55 Z MohamedAhmed04 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 126 ms 18788 KB 
#include <bits/stdc++.h>

using namespace std ;

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 ;
	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)
		{
			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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 0 ms 328 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 27 ms 16596 KB Output is correct
3 Correct 26 ms 16600 KB Output is correct
4 Correct 24 ms 16572 KB Output is correct
5 Correct 25 ms 16616 KB Output is correct
6 Correct 25 ms 16724 KB Output is correct
7 Correct 26 ms 16852 KB Output is correct
8 Correct 23 ms 16980 KB Output is correct
9 Correct 26 ms 17068 KB Output is correct
10 Correct 25 ms 17072 KB Output is correct
11 Correct 28 ms 17024 KB Output is correct
12 Correct 27 ms 17112 KB Output is correct
13 Correct 27 ms 16980 KB Output is correct
14 Correct 29 ms 17120 KB Output is correct
15 Correct 28 ms 17036 KB Output is correct
16 Correct 28 ms 16980 KB Output is correct
17 Correct 25 ms 16908 KB Output is correct
18 Correct 25 ms 16852 KB Output is correct
19 Correct 24 ms 16908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 18244 KB Output is correct
2 Correct 90 ms 18124 KB Output is correct
3 Correct 95 ms 18212 KB Output is correct
4 Correct 79 ms 18176 KB Output is correct
5 Correct 81 ms 18196 KB Output is correct
6 Correct 81 ms 18168 KB Output is correct
7 Correct 80 ms 18164 KB Output is correct
8 Correct 90 ms 18428 KB Output is correct
9 Correct 123 ms 18544 KB Output is correct
10 Correct 126 ms 18584 KB Output is correct
11 Correct 123 ms 18576 KB Output is correct
12 Correct 122 ms 18648 KB Output is correct
13 Correct 116 ms 18644 KB Output is correct
14 Correct 108 ms 18244 KB Output is correct
15 Correct 89 ms 18124 KB Output is correct
16 Correct 89 ms 18104 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 18316 KB Output is correct
2 Correct 73 ms 18316 KB Output is correct
3 Correct 69 ms 18224 KB Output is correct
4 Correct 68 ms 18340 KB Output is correct
5 Correct 114 ms 18568 KB Output is correct
6 Correct 95 ms 18736 KB Output is correct
7 Correct 95 ms 18776 KB Output is correct
8 Correct 96 ms 18644 KB Output is correct
9 Correct 88 ms 18640 KB Output is correct
10 Correct 88 ms 18692 KB Output is correct
11 Correct 88 ms 18704 KB Output is correct
12 Correct 88 ms 18748 KB Output is correct
13 Correct 86 ms 18696 KB Output is correct
14 Correct 99 ms 18764 KB Output is correct
15 Correct 97 ms 18788 KB Output is correct
16 Correct 98 ms 18688 KB Output is correct
17 Correct 105 ms 18688 KB Output is correct
18 Correct 99 ms 18636 KB Output is correct
19 Correct 94 ms 18728 KB Output is correct
20 Correct 84 ms 18408 KB Output is correct
21 Correct 71 ms 18372 KB Output is correct
22 Correct 76 ms 18508 KB Output is correct
23 Correct 66 ms 18304 KB Output is correct