제출 #995540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995540		thelegendary08	밀림 점프 (APIO21_jumps)	C++14	25 / 100	720 ms	60244 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];
	if(n <= 2000){
		f0r(i, n){
			for(int j = i-1;j>=0;j--){
				if(v[j] > v[i]){
					adj[i].pb(j);
					break;
				}
			}
		}
		
		f0r(i, n){
			for(int j = i+1;j<n;j++){
				if(v[j] > v[i]){
					adj[i].pb(j);
					break;
				}
			}
		}
		
		
		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)return C - B;
	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: 4 / 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