Submission #740484

#	Time	Username	Problem	Language	Result	Execution time	Memory
740484		Berryisbetter	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	228 ms	6432 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
vector<ll> seg,br,d;ll n;
ll qw(ll a,ll b){
	ll ans=0;
	for (a+=n,b+=n;a<b;a/=2,b/=2){
		if (a%2){
			ans=max(ans,seg[a]);
			a++;
		}
		if (b%2){
			b--;
			ans=max(ans,seg[b]);
		}
	}
	return ans;
}
ll ind(ll v,ll a,ll b){
	if (a==b){
		return a;
	}
	ll m=(a+b)/2;
	if (qw(a,m)>=v){
		return ind(v,a,m);
	}
	return ind(v,m+1,b);
}
/*#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ll n; cin >> n;
	vector<ll> a(n), r(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
		r[i] = i - 1;
	}
	for (ll i = 0; i < n; i++) {
		ll j = i;
		while (r[j] != -1) {
			if (a[i] > a[r[j]]) {
				break;
			}
			j = r[j];
		}
		r[i] = r[j];
		cout << r[i] + 1 << '\n';
	}
}*/

void init(int N, std::vector<int> H) {
	n=N;
	seg=vector<ll>(2*n,0);
	//segment setup
	for (ll i=0;i<n;i++){
		seg[i+n]=H[i];
	}
	for (ll i=n;i>0;i--){
		seg[i]=max(seg[2*i],seg[2*i+1]);
	}
	//br setup
	br=vector<ll>(n,0);for (ll i=0;i<n;i++){br[i]=i+1;}
	for (ll i = n-1; i >= 0; i--) {
		ll j = i;
		while (br[j] != n) {
			if (H[i] < H[br[j]]) {
				break;
			}
			j = br[j];
		}
		br[i] = br[j];
	}
	//distance
	d=vector<ll>(n+1);d[n]=0;
	for (ll i=0;i<n;i++){
		d[i]=d[br[i]]+1;
	}
}
//ind,qw,d
int minimum_jumps(int A, int B, int C, int D) {
	ll x=ind(seg[B+n],seg[C+n],seg[D+n]);
	if (d[B]>d[x]){
		return d[B]-d[x];
	}
	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