Submission #825591

#	Time	Username	Problem	Language	Result	Execution time	Memory
825591		MohamedAhmed04	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	126 ms	18788 KiB

railway_trip

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55