Submission #1088167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088167		Math4Life2020	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	189 ms	157040 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 262144;
ll N; vector<int> H;
const ll INF = 1e18;
const ll E = 17;
int mx[Nm][E+1]; //first,log2(len)
ll l2(ll x) {
	return (31-__builtin_clz(x));
}
void mwipe() { //wipes memory
	for (ll i=0;i<Nm;i++) {
		for (ll j=0;j<=E;j++) {
			mx[i][j]=-INF;
		}
	}
}
int gm(ll a, ll b) {
	ll D = b-a+1; ll lD = l2(D); ll lDe = (1LL<<lD);
	return max(mx[a][lD],mx[b-lDe+1][lD]);
}
ll lpt[Nm]; ll rpt[Nm]; bool el[Nm];
ll bjr[Nm][E+1]; //binary jump, go right
ll bjt[Nm][E+1]; //total binary jump

pii bst(ll x0, ll T) { //find max height <=T that is reachable: return {position, #(steps)}
	ll x = x0;
	ll e = E;
	ll d = 0;
	while (e>=0) {
		if (bjt[x][e]<=T) {
			x=bjt[x][e]; d+=(1LL<<e);
		}
		e--;
	}
	return {x,d};
}

ll bsr(ll x0, ll T) { //find height >= T
	ll x = x0;
	ll e = E;
	ll d = 0;
	while (e>=0) {
		if (bjr[x][e]<=T) {
			x=bjr[x][e]; d+=(1LL<<e);
		}
		e--;
	}
	return d;
}

void init(int N1, vector<int> H1) {
	mwipe();
	N=N1; H=H1;
	for (ll i=0;i<N;i++) {
		mx[i][0]=H[i];
	}
	for (ll e=1;e<=E;e++) {
		for (ll x=0;x<=(Nm-(1LL<<E));x++) {
			mx[x][e]=max(mx[x][e-1],mx[x+(1LL<<(e-1))][e-1]);
		}
	}
	map<ll,ll> al;
	al[INF]=INF;
	for (ll i=0;i<N;i++) {
		auto A = al.upper_bound(H[i]);
		lpt[i]=(*A).second;
		al[H[i]]=i;
		A = al.find(H[i]);
		while (A != al.begin()) {
			auto B = prev(A);
			if ((*B).second<(*A).second) {
				al.erase(B);
			} else {
				break;
			}
		}
	}
	map<ll,ll> ar;
	ar[INF]=INF;
	for (ll i=(N-1);i>=0;i--) {
		auto A = ar.upper_bound(H[i]);
		rpt[i]=(*A).second;
		ar[H[i]]=i;
		A = ar.find(H[i]);
		while (A != ar.begin()) {
			auto B = prev(A);
			if ((*B).second>(*A).second) {
				ar.erase(B);
			} else {
				break;
			}
		}
	}
	for (ll i=0;i<N;i++) {
		if (lpt[i]==INF || rpt[i]==INF) {
			el[i]=0;
		}
		if (lpt[i]!=INF && rpt[i]!=INF) {
			if (H[lpt[i]]<H[rpt[i]]) {
				lpt[i]=INF; el[i]=0;
			} else {
				el[i]=1;
			}
		}
		if (el[i]) {
			bjt[i][0]=lpt[i];
			bjr[i][0]=rpt[i];
		} else {
			bjt[i][0]=rpt[i];
			bjr[i][0]=rpt[i];
		}
	}
	for (ll e=1;e<=E;e++) {
		for (ll i=0;i<N;i++) {
			if (bjt[i][e-1]==INF) {
				bjt[i][e]=INF;
			} else {
				bjt[i][e]=bjt[bjt[i][e-1]][e-1];
			}
			if (bjr[i][e-1]==INF) {
				bjr[i][e]=INF;
			} else {
				bjr[i][e]=bjr[bjr[i][e-1]][e-1];
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	assert(A==B); assert(C==D);
	if (gm(A,C-1)>H[C]) {
		return -1;
	}
	pii p1 = bst(A,H[C]);
	return (p1.second+bsr(p1.first,H[C]));
}

/*int main() {
	init(7,{3,2,1,6,4,5,7});
	cout << minimum_jumps(4,4,6,6) <<"\n";
	//cout << minimum_jumps(1,3,5,6) <<"\n";
	//cout << minimum_jumps(0,1,2,2) <<"\n";
}*/

Compilation message (stderr)

jumps.cpp: In function 'void mwipe()':
jumps.cpp:16:13: warning: overflow in conversion from 'long long int' to 'int' changes value from '-1000000000000000000' to '1486618624' [-Woverflow]
   16 |    mx[i][j]=-INF;
      |             ^~~~

• 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