제출 #998168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998168		thelegendary08	밀림 점프 (APIO21_jumps)	C++14	21 / 100	4066 ms	84076 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];
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;
	}
	
	set<int>s;
	for(int i = n; i>=1;i--){
		auto it = lower_bound(s.begin(), s.end(), dex[i]);
		if(it != s.begin()){
			adj[dex[i]].pb(*--it);
			it++;
		}
		
		if(it != s.end())adj[dex[i]].pb(*it);
		s.insert(dex[i]);
		//for(auto u : adj[dex[i]])cout<<u<<' ';
		//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(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;
		
	}
}

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