Submission #1077185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077185		thelegendary08	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2056 ms	13932 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<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.rbegin(), w.rend());
	vi l(n, -1);
	vi r(n, -1);
	vi cur;
	int mode = w[0].first;
	f0r(i, n){
		if(w[i].first == mode){
			cur.pb(w[i].second);
		}
		else{
			for(auto u : cur){
				auto it = s.order_of_key(u);
				if(it - 1 >= 0 && it - 1 < s.size())l[u] = *s.find_by_order(it-1);
				else l[u] = -1;
				//it++;
				if(it >= 0 && it < s.size())r[u] = *s.find_by_order(it);
				else r[u] = -1;
			}
			for(auto u : cur)s.insert(u);
			mode = w[i].first;
			cur = {w[i].second};
		}
	}
	if(cur.size() > 0){
		for(auto u : cur){
			auto it = s.order_of_key(u);
			if(it - 1 >= 0 && it - 1 < s.size())l[u] = *s.find_by_order(it-1);
			else l[u] = -1;
			//it++;
			if(it >= 0 && it < s.size())r[u] = *s.find_by_order(it);
			else r[u] = -1;
		}
	}
	
	//f0r(i, n)cout<<r[i]<<' ';
	//cout<<'\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;
			int p = node + 1;
			while(p != -1 && p < n && mx < v[node]){
				nxt.pb(p);
				mx = v[p];
				p = r[p];
				
			}
			
			mx = 0;
			p = node - 1;
			
			while(p >= 0 && mx < v[node]){
				nxt.pb(p);
				mx = v[p];
				p = l[p];
				
			}
			
			
			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;
				}
			}
			
		}
		//f0r(i, n)cout<<dist[i]<<' ';
		//cout<<'\n';
		cout<<dist[b]-1<<'\n';
		
	}
	
}

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