Submission #998279

#	Time	Username	Problem	Language	Result	Execution time	Memory
998279		thelegendary08	Rainforest Jumps (APIO21_jumps)	C++14	56 / 100	4059 ms	141900 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
#define ll long long int
#define vi vector<ll>
using namespace std;
const int mxn = 200005;
int v[mxn];
int n;
vi adj[mxn];
vector<vi> l(18, vi(mxn, 1e9));
vector<vi> h(18, vi(mxn, 1e9));

const int mxn2 = 2005;
int dist[mxn2][mxn2];
int tree[mxn2][mxn2 * 4];
void upd(int dex, int pos, int num){
	pos += n;
	tree[dex][pos] = num;
	for(pos/=2; pos >= 1; pos/=2){
		tree[dex][pos] = min(tree[dex][pos * 2], tree[dex][pos * 2 + 1]);
	}
}
int quer(int dex, int l, int r){
	l += n; r+=n;
	int ret = 1e9;
	while(l <= r){
		if(l % 2 == 1){
			ret = min(ret, tree[dex][l++]);
		}
		if(r % 2 == 0){
			ret = min(ret, tree[dex][r--]);
		}
		l/=2;
		r/=2;
	}
	return ret;
}

void init(int N, std::vector<int> H) {
	n = N;
	f0r(i,N)v[i] = H[i];
	int dex[n+1];
	f0r(i,n){
		dex[v[i]] = i;
	}
	
	stack<int>s;
	f0r(i, n){
		while(!s.empty() && v[s.top()] < v[i]){
			s.pop();
		}
		if(!s.empty())adj[i].pb(s.top());
		s.push(i);
	}
	s = stack<int>();
	for(int i = n-1;i>=0;i--){
		while(!s.empty() && v[s.top()] < v[i]){
			s.pop();
		}
		if(!s.empty())adj[i].pb(s.top());
		s.push(i);
	}
	f0r(i,n){
		if(adj[i].size() == 1)l[0][i] = adj[i][0];
		else if(adj[i].size() == 2){
			if(v[adj[i][0]] > v[adj[i][1]]){
				l[0][i] = adj[i][1];
				h[0][i] = adj[i][0];
			}
			else{
				h[0][i] = adj[i][1];
				l[0][i] = adj[i][0];
			}
		}
	}
	
	for(int i = 1;i<18;i++){
		f0r(j, n){
			if(l[i-1][j] != 1e9)l[i][j] = l[i-1][l[i-1][j]];
			if(h[i-1][j] != 1e9)h[i][j] = h[i-1][h[i-1][j]];
		}
	}
	f0r(i, 18){
		f0r(j, n){
			//cout<<l[i][j]<<' ';
			
		}
		//cout<<'\n';
	}
	if(n <= 2000){
		f0r(i, n)f0r(j,n)dist[i][j] = 1e9;
		f0r(i,n){
			queue<int>q;
			dist[i][i] = 0;
			vector<bool>vis(n, false);
			vis[i] = 1;
			q.push(i);
			while(!q.empty()){
				int cur = q.front();
				q.pop();
				for(auto u : adj[cur]){
					 if(vis[u])continue;
					 vis[u] = 1;
					 q.push(u);
					 dist[i][u] = min(dist[i][cur] + 1, dist[i][u]);
				}
			}
		}
		f0r(i, n){
			f0r(j, n){
				upd(i, j, dist[i][j]);
			}
		}
	}
	
}

int minimum_jumps(int A, int B, int C, int D) {
	if(A == B && C == D){
		int cur = A;
		int t = D;
		int ans = 0;
		for(int i = 17;i>=0;i--){
			if(h[i][cur] < n && v[h[i][cur]] <= v[t]){
				cur = h[i][cur];
				ans += (1 << i);
			}
		}
		for(int i = 17; i>=0; i--){
			if(l[i][cur] < n && v[l[i][cur]] <= v[t]){
				cur = l[i][cur];
				ans += (1 << i);
			}
		}
		if(cur != t)return -1;
		else return ans;
	}
	else if(n > 2000){
		vector<bool>vis(n, 0);
		vi dist(n);
		queue<int>q;
		for(int i = A;i<=B;i++){
			dist[i] = 0;
			vis[i] = 1;
			q.push(i);
		}
		bool stop = 0;
		int ans = 0;
		while(!(stop || q.empty())){
			int c = q.front();
			q.pop();
			for(auto u : adj[c]){
				if(vis[u])continue;
				vis[u] = 1;
				dist[u] = dist[c] + 1;
				q.push(u);
				if(u >= C && u <= D){
					ans = u;
					stop = 1;
				}
			}
		}
		if(!stop)return -1;
		else return dist[ans];
	}
	
	else{
		int ans = 1e9;
		for(int i = A; i<=B;i++){
			ans = min(ans, quer(i, C, D));
		}
		if(ans == 1e9)return -1;
		else return ans;
		
	}
	
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:44:6: warning: variable 'dex' set but not used [-Wunused-but-set-variable]
   44 |  int dex[n+1];
      |      ^~~

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19