Submission #1090396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090396		pan	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	181 ms	97588 KiB

jumps

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define show4(x,y,z, a) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << " " << #a << " is " << a << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef __int128 ull;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;


ll n, h[200005], a, b, c, d;

ll twokr[200005][25],twokl[200005][25], hi[200005][25];

void init(int N, std::vector<int> H)
{
	n = N;
	h[0] = h[n+1] = LLONG_MAX;
	twokl[0][0] = twokl[n+1][0] = 0, hi[0][0] = hi[n+1][0] = twokr[0][0] = twokr[n+1][0] = n+1;
	for (ll i=1;i <=n; ++i) h[i] = H[i-1];
	deque<ll> mono; // monotonically decreasing queue
	for (ll i=1; i<=n; ++i)
	{
		if (mono.size() && h[mono.back()] <= h[i]) mono.pop_back();
		twokl[i][0] = (mono.size()?mono.back(): i);
		//show2(i, twokl[i][0]);
		mono.pb(i);
	}
	mono.clear();
	for (ll i=n ;i>=1; --i)
	{
		if (mono.size() && h[mono.back()] <= h[i]) mono.pop_back();
		twokr[i][0] = (mono.size()?mono.back(): i);
		//show2(i, twokr[i][0]);
		hi[i][0] = ((h[twokl[i][0]]>h[twokr[i][0]])?twokl[i][0]:twokr[i][0]);
		mono.pb(i);
	}
	// binary jumping
	for (ll i=1; i<=18; ++i) 
	{
		for (ll j=0; j<=n+1; ++j)
		{
			twokl[j][i] = twokl[twokl[j][i-1]][i-1];
			twokr[j][i] = twokr[twokr[j][i-1]][i-1];
			hi[j][i] = hi[hi[j][i-1]][i-1];
		}
	}
	
}

ll query(ll l, ll r)
{
	//show2(l, r);
	for (ll k=18; k>=0; --k)
	{
		if (twokr[l][k] > r) continue;
		l = twokr[l][k];
	}
	return l;
}
int minimum_jumps(int A, int B, int C, int D)
{
	a = A+1, b = B+1, c = C + 1, d = D+1;
	// start with c 
	// c is either optmimal (low h) or need to be pass through (high h)
	if (b+1 == c) // already adjacent, no need to 'swing' around
	{
		if (twokr[b][0] <= d) return 1;
		return -1;
	}
	ll b4 = query(b+1, c-1);
	if (h[b] > h[b4]) // ready to jump
	{
		if (twokr[b][0] <= d) return 1;
		return -1;
	}
	ll st = b;
	// go up as much as possible for free
	for (ll i=18; i>=0; --i)
	{
		if (twokl[st][i] < a || h[twokl[st][i]] > h[b4]) continue;
		st = twokl[st][i];
	}
	// if already ready to jump
	if (twokl[st][0] >= a && twokr[twokl[st][0]][0] <= d) return 1;
	ll ans = 0;
	if (twokl[st][0] < a)
	{
		//show(st);
		//for (ll i=1; i<18; ++i) show(hi[4][i]);
		// choose to jump to highest one until just before it reach b4
		for (ll i=18; i>=0; --i)
		{
			//show(hi[st][i]);
			if (h[hi[st][i]] >= h[b4]) continue;
			st = hi[st][i];
			//show(st);
			ans += (1LL << i);
		}
		//show2(ans, st);
		if (st == b4) // just nice at b4
		{
			if (twokr[st][0] <= d) return ans + 1;
			return -1;
		}
		// take care of edges case
		if (twokr[st][0] >= c && twokr[st][0] <= d) return ans + 1;
		if (0 < twokl[st][0] &&  c <= twokr[twokl[st][0]][0]  && twokr[twokl[st][0]][0] <= d) return ans + 2;
	}
	// last jump
	for (ll j=18; j>=0; --j)
	{
		if (twokr[st][j] >= c) continue;
		ans += (1LL<< j);
		st = twokr[st][j];
	}
	if (twokr[st][0] >= c && twokr[st][0] <= d) return ans + 1;
	return -1;
}

• 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