제출 #978831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978831		Mher777	밀림 점프 (APIO21_jumps)	C++17	48 / 100	950 ms	101636 KiB

jumps

#include "jumps.h"
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);

/* -------------------- Constants -------------------- */

const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(2e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

const int N = 200005, M = 30;
int a[N], dpl[N], dpr[N], tol[N], toh[N], upl[N][M], uph[N][M];
pii st[N][M];
int n, l1, r1, l2, r2, lg;

pii qry_max(int l, int r) {
	int lgx = log2(r - l + 1);
	return max(st[l][lgx], st[r - (1 << lgx) + 1][lgx]);
}

void init(int N, std::vector<int> H) {
	n = N;
	lg = log2(n);
	vector<pii> v;
	for (int i = 0; i < n; ++i) {
		a[i + 1] = H[i];
		st[i + 1][0] = { a[i + 1],i + 1 };
		v.pub({ a[i + 1],i + 1 });
	}
	for (int l = 1; l <= lg; ++l) {
		for (int i = 1; (i + (1 << l) - 1) <= n; ++i) {
			st[i][l] = max(st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
		}
	}
	sort(all(v));
	reverse(all(v));
	for (int i = 1; i <= n; ++i) {
		int ind = i - 1;
		while (ind && a[ind] <= a[i]) {
			ind = dpl[ind];
		}
		dpl[i] = ind;
	}
	for (int i = n; i >= 1; --i) {
		int ind = i + 1;
		while (ind <= n && a[ind] <= a[i]) {
			ind = dpr[ind];
		}
		dpr[i] = ind;
		if (dpl[i] != 0 && dpr[i] != n + 1) {
			tol[i] = dpl[i];
			toh[i] = dpr[i];
			if (a[dpl[i]] > a[dpr[i]]) {
				swap(tol[i], toh[i]);
			}
		}
		else if (dpl[i]) {
			tol[i] = dpl[i];
			toh[i] = MAX;
		}
		else if (dpr[i] != n + 1) {
			tol[i] = dpr[i];
			toh[i] = MAX;
		}
		else {
			tol[i] = toh[i] = MAX;
		}
	}
	for (auto elem : v) {
		int ind = elem.ss;
		if (tol[ind] == MAX) {
			for (int l = 0; l <= lg; ++l) {
				upl[ind][l] = uph[ind][l] = MAX;
			}
			continue;
		}
		upl[ind][0] = tol[ind];
		for (int l = 1; l <= lg; ++l) {
			if (upl[ind][l - 1] == MAX) {
				upl[ind][l] = MAX;
				continue;
			}
			upl[ind][l] = upl[upl[ind][l - 1]][l - 1];
		}
		if (toh[ind] == MAX) {
			for (int l = 0; l <= lg; ++l) {
				uph[ind][l] = MAX;
			}
			continue;
		}
		uph[ind][0] = toh[ind];
		for (int l = 1; l <= lg; ++l) {
			if (uph[ind][l - 1] == MAX) {
				uph[ind][l] = MAX;
				continue;
			}
			uph[ind][l] = uph[uph[ind][l - 1]][l - 1];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	++A, ++B, ++C, ++D;
	l1 = A, r1 = B, l2 = C, r2 = D;
	int ind = -1;
	int lx = l1, rx = r1;
	while (lx <= rx) {
		int mid = (lx + rx) / 2;
		pii p = qry_max(mid, r1);
		if (p.ff > a[l2]) {
			lx = mid + 1;
		}
		else {
			ind = p.ss;
			rx = mid - 1;
		}
	}
	if (ind == -1) return -1;
	int h = a[l2];
	int ans = 0;
	for (int l = lg; l >= 0; --l) {
		if (uph[ind][l] == MAX) continue;
		if (a[uph[ind][l]] <= h) {
			ind = uph[ind][l];
			ans += (1 << l);
		}
	}
	for (int l = lg; l >= 0; --l) {
		if (upl[ind][l] == MAX) continue;
		if (a[upl[ind][l]] <= h) {
			ind = upl[ind][l];
			ans += (1 << l);
		}
	}
	if (a[ind] != h) return -1;
	return ans;
}

/*
7 100
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/

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