Submission #1088193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088193		Math4Life2020	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4046 ms	100772 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]=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();
	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++) {
		ll rminv = INF;
		for (ll j=(N-1);j>i;j--) {
			if (H[j]>H[i]) {
				rminv=j;
			}
		}
		if (rminv!=rpt[i]) {
			cout << "failed\n";
		}
		ll lmaxv = INF;
		for (ll j=0;j<i;j++) {
			if (H[j]>H[i]) {
				lmaxv=j;
			}
		}
		if (lmaxv!=lpt[i]) {
			cout << "failed\n";
		}
	}*/
	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 mj0(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]);
	//cout << "xf="<<p1.first<<", #(steps)="<<p1.second<<"\n";
	return (p1.second+bsr(p1.first,H[C]));
}

int minimum_jumps(int A, int B, int C, int D) {
	vector<int> fadj[N];
	bool found[N];
	for (ll i=0;i<N;i++) {
		found[i]=0;
		if (rpt[i]!=INF) {
			fadj[i].push_back(rpt[i]);
		}
		if (lpt[i]!=INF) {
			fadj[i].push_back(lpt[i]);
		}
	}
	priority_queue<pii> pq; //{-time,pos}
	//pq.push({0,A});
	for (ll k=A;k<=B;k++) {
		pq.push({0,k});
	}
	while (!pq.empty()) {
		pii pn = pq.top(); pq.pop();
		ll t = -pn.first; ll x = pn.second;
		if (x>=C && x<=D) {
			return t;
		}
		if (!found[x]) {
			found[x]=1;
			for (ll y: fadj[x]) {
				pq.push({-t-1,y});
			}
		}
	}
	return -1;
}

/*int main() {
	mt19937 gen((long long) new char);
	int N1 = 2000;
	map<ll,ll> selem;
	while ((int)selem.size()<N1) {
		selem[gen()]=gen();
	}
	vector<pii> velem1;
	for (pii p0: selem) {
		velem1.push_back({p0.second,p0.first});
	}
	sort(velem1.begin(),velem1.end());
	vector<int> velem;
	for (pii p0: velem1) {
		velem.push_back(p0.second);
	}
	init(N1,velem);
	for (ll t=0;t<(5*N1);t++) {
		ll a = gen()%N1; ll c = gen()%N1;
		//cout << "a,c="<<a<<","<<c<<"\n";
		if (a>c) swap(a,c);
		if (a==c) {
			continue;
		}
		//cout << minimum_jumps(a,a,c,c) <<"\n";
		if (mj2(a,a,c,c)!=minimum_jumps(a,a,c,c)) {
			cout << "broken\n";
		}
	}
}*/

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