Submission #1077168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077168		thelegendary08	Railway Trip (JOI17_railway_trip)	C++17	5 / 100	2095 ms	6100 KiB

railway_trip

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define mii map<int,int>
#define mll map<long long int, long long int>
#define mivi map<int,vector<int>>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> os;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	int n,k,q;
	cin>>n>>k>>q;
	
	vi v(n);
	f0r(i, n)cin>>v[i];
	os s;
	vpii w(n);
	f0r(i, n){
		w.pb({v[i], i});
	}
	sort(w.begin(), w.end());
	f0r(i, n){
		
	}
	while(q--){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		//if(v[a] > v[b])swap(a, b);
		queue<int>q;
		q.push(a);
		//do we need to calculate l[a] and r[a] for each a to make it faster?
		//yes
		//insert from low to high, do lowerbound to find left and right?
		//pbds probably needed
		vi dist(n, 4e18);
		dist[a] = 0;
		vb vis(n, 0);
		vis[a] = 1;
		while(!q.empty()){
			int node = q.front();
			q.pop();
			vi nxt;
			int mx = 0;
			for(int i = node + 1; i < n; i++){
				if(v[i] > mx){
					mx = v[i];
					nxt.pb(i);
				}
				if(mx >= v[node])break;
			}
			mx = 0;
			for(int i = node - 1; i>=0; i--){
				if(v[i] > mx){
					mx = v[i];
					nxt.pb(i);
				}
				if(mx >= v[node])break;
			}
			
			for(auto u : nxt){
				if(!vis[u]){
					q.push(u);
					vis[u] = 1;
					dist[u] = min(dist[u], dist[node] + 1);
					if(u == b)break;
				}
			}
			/*
			if(nl != -1 && !vis[nl]){
				q.push(nl);
				vis[nl] = 1;
				dist[nl] = min(dist[nl], dist[node] + 1);
				if(nl == b)break;
			}
			if(nr != -1 && !vis[nr]){
				q.push(nr);
				vis[nr] = 1;
				dist[nr] = min(dist[nr], dist[node] + 1);
				if(nr == b)break;
			}
			*/
		}
		//f0r(i, n)cout<<dist[i]<<' ';
		//cout<<'\n';
		cout<<dist[b]-1<<'\n';
		
	}
}

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