Submission #1088189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088189		Math4Life2020	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	206 ms	70844 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)
int l2(int 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]=0;
		}
	}
}
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]!=INF && H[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]!=INF && H[bjr[x][e]]<=T) {
			x=bjr[x][e]; d+=(1LL<<e);
		}
		e--;
	}
	return d;
}

void init(int N1, vector<int> H1) {
	//mwipe();
	H.clear();
	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];
		}
		//cout << "i="<<i<<", lpt[i]="<<lpt[i]<<", rpt[i]="<<rpt[i]<<"\n";
	}
	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];
			}
		}
	}
	/*for (ll i=0;i<N;i++) {
		cout << "i="<<i<<"\n";
		for (ll e=0;e<=E;e++) {
			cout << "e="<<e<<", bjt="<<bjt[i][e]<<", bjr="<<bjr[i][e]<<"\n";
		}
	}*/
}

int minimum_jumps(int A, int B, int C, int D) {
	if (gm(A,C-1)>H[C]) {
		assert(1==2);
		return -1;
	}
	pii p1 = bst(A,H[C]);
	//cout << "xf="<<p1.first<<", #(steps)="<<p1.second<<"\n";
	return (p1.second+bsr(p1.first,H[C]));
}

• 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