oj.uz

Submission #345876

# Submission time Handle Problem Language Result Execution time Memory
345876 2021-01-08T11:06:37 Z kshitij_sodani Railway Trip (JOI17_railway_trip) C++14
0 / 100
 2000 ms 8172 KB 
//#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);
				//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);
			//	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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