oj.uz

Submission #1077168

# Submission time Handle Problem Language Result Execution time Memory
1077168 2024-08-27T02:19:49 Z thelegendary08 Railway Trip (JOI17_railway_trip) C++17
5 / 100
 2000 ms 6100 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_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.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 348 KB Output is correct
5 Correct 0 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 1 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 425 ms 5172 KB Output is correct
3 Correct 482 ms 5180 KB Output is correct
4 Correct 494 ms 5436 KB Output is correct
5 Correct 507 ms 5440 KB Output is correct
6 Correct 548 ms 5436 KB Output is correct
7 Correct 580 ms 5684 KB Output is correct
8 Correct 206 ms 5184 KB Output is correct
9 Execution timed out 2066 ms 5696 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 2095 ms 5428 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 2003 ms 6100 KB Time limit exceeded
2 Halted 0 ms 0 KB -