제출 #438642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438642		AriaH	밀림 점프 (APIO21_jumps)	C++11	100 / 100	1972 ms	50988 KiB

jumps

#include "jumps.h"
/** vaziat sorati ghermeze **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int h[N], L[LOG][N], R[LOG][N], best[LOG][N];

void init(int n, vector < int > H)
{
	for(int i = 0; i < n; i ++) { h[i + 1] = H[i]; }
	h[0] = h[n + 1] = 2e9;
	deque < int > dq;
	n += 2;
	for(int i = 0; i < n; i ++)
	{
		while(SZ(dq) && h[dq.back()] <= h[i]) dq.pop_back();
		L[0][i] = (dq.empty()? i : dq.back());
		dq.push_back(i);
	}
	dq.clear();
	for(int i = n; i >= 0; i --)
	{
		while(SZ(dq) && h[dq.back()] <= h[i]) dq.pop_back();
		R[0][i] = (dq.empty()? i : dq.back());
		dq.push_back(i);
	}
	for(int i = 1; i <= n; i ++)
	{
		best[0][i] = (h[L[0][i]] > h[R[0][i]]? L[0][i] : R[0][i]);
	}
	for(int T = 1; T < LOG; T ++)
	{
		for(int i = 1; i <= n; i ++)
		{
			L[T][i] = L[T - 1][L[T - 1][i]];
			R[T][i] = R[T - 1][R[T - 1][i]];
			best[T][i] = best[T - 1][best[T - 1][i]];
		}
	}
}

inline int get(int l, int r)
{
	for(int T = LOG - 1; ~T; T --) { if(R[T][l] <= r) l = R[T][l]; }
	return l;
}

int minimum_jumps(int A, int B, int C, int D)
{
	A ++, B ++, C ++, D ++;
	if(B + 1 == C)
	{
		return (R[0][B] > D? -1 : 1);
	}
	int mid = get(B + 1, C - 1);
	///printf("mid = %d\n", mid);
	if(h[B] > h[mid])
	{
		return (R[0][B] > D? -1 : 1);
	}
	for(int T = LOG - 1; ~T; T --)
	{
		if(L[T][B] >= A && h[L[T][B]] < h[mid]) B = L[T][B];
	}
	///printf("B = %d\n", B);
	int tot = 0;
	if(A <= L[0][B])
	{
		if(R[0][L[0][B]] <= D) return 1;
	}
	else
	{
		for(int T = LOG - 1; ~T; T --)
		{
			///printf("T = %d B = %d best = %d\n", T, B, best[T][B]);
			if(h[best[T][B]] <= h[mid])
			{
				tot += 1 << T;
				B = best[T][B];
			}
		}
		if(B == mid)
		{
			return (R[0][B] <= D? ++tot : -1);
		}
		if(L[0][B] && R[0][L[0][B]] <= D)
		{
			return tot + 2;
		}
	}
	///printf("tot = %d\n", tot);
	for(int T = LOG - 1; ~T; T --)
	{
		if(R[T][B] < C)
		{
			tot += 1 << T;
			B = R[T][B];
		}
	}
	if(C <= R[0][B] && R[0][B] <= D) return tot + 1;
	return -1;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

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