Submission #916180

#	Time	Username	Problem	Language	Result	Execution time	Memory
916180		KiaRez	Rainforest Jumps (APIO21_jumps)	C++17	27 / 100	833 ms	60968 KiB

jumps

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 2e5+23, lg = 18;

int n, l[N], r[N], f[lg][N], f2[lg][N], spl[lg][N], spr[lg][N], h[N];
void init(int _n, vector<int> _h) {
	n=_n; for(int i=1; i<=n; i++) h[i] = _h[i-1];

	h[0] = 1e9+1, h[n+1] = 1e9+2;
	for(int i=1; i<=n; i++) {
		l[i] = i-1;
		while(h[i] > h[l[i]]) l[i] = l[l[i]];
		spl[0][i] = i;
		for(int j=1; j<lg; j++) {
			int x=spl[j-1][i], y=spl[j-1][max(0,i-(1<<(j-1)))];
			spl[j][i] = (h[x]>h[y] ? x : y);
		}
	}

	for(int i=0; i<lg; i++) f2[i][n+1] = f[i][n+1] = spr[i][n+1] = n+1;
	for(int i=n; i>=1; i--) {
		r[i] = i+1;
		while(h[i] > h[r[i]]) r[i] = r[r[i]];
		
		if(l[i]==0 || (r[i]<=n && h[r[i]] > h[l[i]])) f[0][i] = r[i], f2[0][i] = r[i];
		else f[0][i] = l[i], f2[0][i] = r[i];
		
		spr[0][i] = i;
		for(int j=1; j<lg; j++) {
			int x=spr[j-1][i], y=spr[j-1][min(n+1,i+(1<<(j-1)))];
			spr[j][i] = (h[x]>h[y] ? x : y);
		}
	}

	for(int i=1; i<lg; i++) {
		for(int j=1; j<=n; j++) {
			f[i][j] = f[i-1][f[i-1][j]];
			f2[i][j] = f2[i-1][f2[i-1][j]];
		}
	}
}

int minimum_jumps(int a, int b, int c, int d) {
	a++, b++, c++, d++;
	int mxv=n+2, mxu=b, tmp=c, ans=0;
	for(int i=lg-1; i>=0; i--) {
		if(tmp+(1<<i)-1 <= d) mxv = (h[mxv]>h[spr[i][tmp]] ? mxv : spr[i][tmp]), tmp += (1<<i);
	}
	tmp = b;
	for(int i=lg-1; i>=0; i--) {
		if(spl[i][mxu] >= a && h[spl[i][mxu]] < h[mxv]) {
			mxu = spl[i][tmp];
		}
	}

	for(int i=lg-1; i>=0; i--) {
		if(h[f[i][mxu]] < h[mxv] && f[i][mxu] < c && r[f[i][mxu]] < c) ans += (1<<i), mxu = f[i][mxu];
	}
	if(r[mxu] < c && f[0][mxu] < c && h[f[0][mxu]] < h[mxv]) {
		ans ++; mxu = f[0][mxu];
	}
	for(int i=lg-1; i>=0; i--) {
		if(f2[i][mxu] < c) mxu = f2[i][mxu], ans += (1<<i);
	}

	if(mxu >= c && mxu <= d) return ans;
	int res = f2[0][mxu];
	if(res>=c && res<=d) {
		return ans+1;
	}
	return -1;
}

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