Submission #936901

#	Time	Username	Problem	Language	Result	Execution time	Memory
936901		asdf1234coding	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	40 ms	69976 KiB

jumps

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;

// #define UWU

// #define int long long
#define problemname ""
#define pii pair<int,int>
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second

#define tc int t; cin>>t; while(t--) solve();

bool ckmin(int& a, int b) {return a>b?a=b,true:false;}
bool ckmax(int& a, int b) {return a<b?a=b,true:false;}

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 0; // CHECK
const int MX = 2e5;
const int MN = 30;

int succL[MN][MX];
int succR[MN][MX];
int succLR[MN][MX];

void init(int n, vi a) {
	vi stk; 
	for(int i=0; i<n; i++) {
		while(stk.size() && a[stk.back()]<a[i]) {
			cout<<"popped "<<stk.back()<<endl;
			stk.pop_back();
		}
		if(stk.size()) succL[0][i]=stk.back();
		else succL[0][i]=-1;
		stk.pb(i);
	}
	// cout<<"L ";
	// for(int i=0; i<n; i++) {
	// 	cout<<succL[0][i]<<' ';
	// }
	// cout<<endl;
	stk.clear();
	for(int i=n-1; i>=0; i--) {
		while(stk.size() && a[stk.back()]<a[i]) stk.pop_back();
		if(stk.size()) succR[0][i]=stk.back();
		else succR[0][i]=-1;
		stk.pb(i);
	}
	// cout<<"R ";
	// for(int i=0; i<n; i++) {
	// 	cout<<succR[0][i]<<' ';
	// }
	// cout<<endl;

	for(int i=0; i<n; i++) {
		succLR[0][i]=max(succL[0][i], succR[0][i]);
	}

	for(int j=1; j<MN; j++) {
		for(int i=0; i<n; i++) {
			succL[j][i]=succL[j-1][i]!=-1?succL[j-1][succL[j-1][i]]:-1;
			succR[j][i]=succR[j-1][i]!=-1?succR[j-1][succR[j-1][i]]:-1;
			succLR[j][i]=succLR[j-1][i]!=-1?succLR[j-1][succLR[j-1][i]]:-1;
		}
	}

}

int minimum_jumps(int a, int b, int c, int d) {

	int cur=b; // go as left as possible
	// cout<<"start at "<<cur<<endl;
	for(int i=MN-1; i>=0; i--) {
		if(succL[i][cur] >= a && succL[i][cur]!=-1 && succR[0][succL[i][cur]] <= d) {
			cur=succL[i][cur];
		}
	}

	// cout<<"leftest "<<cur<<endl;

	// up :3

	int ret=0;

	for(int i=MN-1; i>=0; i--) {
		// cout<<"suclr "<<succLR[i][cur]<<endl;
		if(succLR[i][cur]!=-1 && succLR[i][cur] < c ){ //&& succR[0][succLR[i][cur]] !=-1) {
			cur=succLR[i][cur];
			ret+=(1ll<<i);
		}
	}

	// cout<<"oneoff "<<cur<<endl;

	if(succLR[0][cur]<=d && succLR[0][cur]>=c) {
		return ret+1;
	}

	for(int i=MN-1; i>=0; i--) {
		if(succR[i][cur]!=-1 && succR[i][cur] < c){ // && succR[0][succR[i][cur]] !=-1) {
			cur=succR[i][cur];
			ret+=(1ll<<i);
		}
	}

	if(succLR[0][cur]<=d && succLR[0][cur]>=c) {
		return ret+1;
	}

	return -1;
}

#ifdef UWU

int32_t main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen (problemname ".in", "r", stdin); freopen(problemname ".out", "w", stdout);
	init(7, {3,2,1,6,4,5,7});
	cout<<minimum_jumps(4, 4, 6, 6)<<endl;
	cout<<minimum_jumps(1, 3, 5, 6)<<endl;
	cout<<minimum_jumps(0, 1, 2, 2)<<endl;
	return 0;
}

#endif

• 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