oj.uz

Submission #1077185

# Submission time Handle Problem Language Result Execution time Memory
1077185 2024-08-27T02:40:27 Z thelegendary08 Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 13932 KB 
#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.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 435 ms 12464 KB Output is correct
3 Correct 474 ms 12856 KB Output is correct
4 Correct 462 ms 13024 KB Output is correct
5 Correct 504 ms 13112 KB Output is correct
6 Correct 497 ms 13212 KB Output is correct
7 Correct 493 ms 13624 KB Output is correct
8 Correct 229 ms 7740 KB Output is correct
9 Correct 301 ms 13368 KB Output is correct
10 Correct 287 ms 11576 KB Output is correct
11 Correct 390 ms 13404 KB Output is correct
12 Correct 413 ms 13364 KB Output is correct
13 Correct 405 ms 13364 KB Output is correct
14 Correct 404 ms 13484 KB Output is correct
15 Correct 458 ms 13368 KB Output is correct
16 Correct 419 ms 13348 KB Output is correct
17 Correct 473 ms 13772 KB Output is correct
18 Correct 468 ms 13620 KB Output is correct
19 Correct 410 ms 13880 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 12848 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 2056 ms 13932 KB Time limit exceeded
2 Halted 0 ms 0 KB -