oj.uz

Submission #345877

# Submission time Handle Problem Language Result Execution time Memory
345877 2021-01-08T11:14:13 Z kshitij_sodani Railway Trip (JOI17_railway_trip) C++14
5 / 100
 2000 ms 8556 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);
				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);
				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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2924 KB Output is correct
2 Correct 198 ms 7708 KB Output is correct
3 Correct 239 ms 8044 KB Output is correct
4 Correct 262 ms 8172 KB Output is correct
5 Correct 258 ms 8220 KB Output is correct
6 Correct 253 ms 8376 KB Output is correct
7 Correct 274 ms 8556 KB Output is correct
8 Correct 80 ms 7136 KB Output is correct
9 Execution timed out 2056 ms 7252 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 7756 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 2052 ms 8044 KB Time limit exceeded
2 Halted 0 ms 0 KB -