Submission #345879

#	Time	Username	Problem	Language	Result	Execution time	Memory
345879		kshitij_sodani	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2057 ms	8644 KiB

railway_trip

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int n,k,q;
int it[100001];
int dis[100001];
vector<int> adj[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	/*for(int i=0;i<n;i++){
		cout<<it[i]<<",";
	}
	cout<<endl;*/
	if(true){
		vector<pair<int,int>> ss;
		for(int i=0;i<n;i++){
			while(ss.size()){
				if(ss.back().a<it[i]){
					ss.pop_back();
					continue;
				}
				else{
					break;
				}
			}
			if(ss.size()){
				adj[i].pb(ss.back().b);
				adj[ss.back().b].pb(i);
				/*int mi=-1;
				for(int j=i-1;j>ss.back().b;j--){
					if(it[j]>mi){
						adj[i].pb(j);
						mi=it[j];
					}
				}*/
				//cout<<i<<","<<ss.back().b<<endl;
			}
			ss.pb({it[i],i});
		}
		ss.clear();
		for(int i=n-1;i>=0;i--){
			while(ss.size()){
				if(ss.back().a<it[i]){
					ss.pop_back();
					continue;
				}
				else{
					break;
				}
			}
			if(ss.size()){
				adj[i].pb(ss.back().b);
				adj[ss.back().b].pb(i);
			/*	if(i+1<ss.back().b){
					adj[i].pb(i+1);
				}*/
				/*int mi=-1;
				for(int j=i+1;j<ss.back().b;j++){
					if(it[j]>mi){
						adj[i].pb(j);
						mi=it[j];
					}
				}*/
				//cout<<i<<":"<<ss.back().b<<endl;
			}
			ss.pb({it[i],i});
		}
	}
	
	while(q--){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		if(it[aa]>it[bb]){
			swap(aa,bb);
		}
		queue<int> ss;
		ss.push(aa);
		for(int i=0;i<n;i++){
			dis[i]=-1;
		}
		dis[aa]=0;

		while(ss.size()){
			int no=ss.front();
			ss.pop();
			for(auto j:adj[no]){
				if(dis[j]==-1){
					dis[j]=dis[no]+1;
					ss.push(j);
				}
			}
		}
		cout<<dis[bb]-1<<endl;
	}





 
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55