제출 #1178404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178404		tkm_algorithms	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	4038 ms	12384 KiB

jumps

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
//#include "jumps.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 2e5;
const int inf = 1e9;

vector<int> g[N+1];

void init(int n, vector<int> h) {
	stack<int> st;
	vector<int> a(n, -1), b(n, -1);
	for (int i = n-1; i >= 0; --i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())a[i] = st.top();
		st.push(i);
	}
	
	while (!st.empty())st.pop();
	
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())b[i] = st.top();
		st.push(i);
	}
	
	for (int i = 0; i < n; ++i) {
		if (a[i] != -1)g[i].push_back(a[i]);
		if (b[i] != -1)g[i].push_back(b[i]);
	}
	
}

int minimum_jumps(int a, int b, int c, int d) {
	queue<pair<int, int>> q;
	for (int i = a; i <= b; ++i)
		q.push({0, i});
	
	int ans = inf;
	while (!q.empty()) {
		int u = q.front().second, w = q.front().first;
		q.pop();
		if (w >= ans)continue;
		if (u >= c && u <= d) {
			ans = min(ans, w);
			continue;
		}
		for (auto i: g[u]) {
			q.push({w+1, i});
		}
	}
	return ans;
}

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