Submission #860255

#	Time	Username	Problem	Language	Result	Execution time	Memory
860255		mychecksedad	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	948 ms	129912 KiB

jumps

#include<jumps.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;


int n, L[N], R[N], up[N][K][2], dp[N][K];
vector<int> H;
vector<array<int, 2>> T[N];
int maxx(int l, int r){
	int k = int(log2(r-l+1));
	return max(dp[l][k], dp[r-(1<<k)+1][k]);
}

void build(int l, int r, int k){
	if(l == r){
		T[k].pb(array<int, 2>{H[l-1], l-1});
		return;
	}
	int m = l+r>>1;
	build(l, m, k<<1);
	build(m+1, r, k<<1|1);
	int p = 0;
	for(int i = 0; i < T[k<<1].size(); ++i){
		while(p < T[k<<1|1].size() && T[k<<1|1][p] < T[k<<1][i]){
			T[k].pb(T[k<<1|1][p]);
			++p;
		}
		T[k].pb(T[k<<1][i]);
	}
	while(p < T[k<<1|1].size())
		T[k].pb(T[k<<1|1][p]), ++p;
	// cout << l << ' ' << r << '\n';
	// for(auto p: T[k]) cout << p[0] << ' ' << p[1] << " | ";
		// en;
}

array<int, 2> get(int l, int r, int ql, int qr, int k, int val){
	if(ql > r || l > qr) return {-1, -1};
	if(ql <= l && r <= qr){
		int pos = lower_bound(all(T[k]), array<int, 2>{val, -1}) - T[k].begin();
		// cout << l << ' ' << r << ' ' << ql << ' ' << qr << ' ' << val << '\n';
		--pos;
		if(pos >= 0){
			// cout << T[k][pos][0] << ' ' << T[k][pos][1] << '\n';
			return T[k][pos];
		}
		return {-1, -1};
	}
	int m = l+r>>1;
	auto L = get(l, m, ql, qr, k<<1, val);
	auto R = get(m+1, r, ql, qr, k<<1|1, val);
	if(L[0] < R[0])
		return R;
	return L;
}

void init(int _n, vector<int> h){
	n = _n;
	H = h;
	
	H.pb(MOD);

	deque<int> q;
	L[0] = n;
	q.pb(0);
	for(int i = 1; i < n; ++i){
		while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
		if(!q.empty()) L[i] = q.back();
		else L[i] = n;
		q.pb(i);
	}
	
	q.clear();
	R[n-1] = n;
	q.pb(n-1);
	for(int i = n-2; i >= 0; --i){
		while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
		if(!q.empty()) R[i] = q.back();
		else R[i] = n;
		q.pb(i);
	}

	for(int i = 0; i < n; ++i) dp[i+1][0] = H[i];
	for(int j = 1; j < K; ++j){
		for(int i = 1; i + (1<<j) <= n + 1; ++i){
			dp[i][j] = max(dp[i][j - 1], dp[i+(1<<(j-1))][j-1]);
		}
	}
	

	up[n][0][0] = n;
	up[n][0][1] = n;
	for(int i = 0; i < n; ++i){
		if(H[L[i]] > H[R[i]]){
			up[i][0][0] = L[i];
			up[i][0][1] = R[i];
		}else{
			up[i][0][1] = L[i];
			up[i][0][0] = R[i];
		}
	}
	for(int j = 1; j < K; ++j){
		for(int i = 0; i <= n; ++i){
			up[i][j][0] = up[up[i][j - 1][0]][j - 1][0];
			up[i][j][1] = up[up[i][j - 1][1]][j - 1][1];
		}
	}

	build(1, n, 1);
}
int minimum_jumps(int A, int B, int C, int D){
	int v = -1, ans = 0;
	int mx = maxx(C+1, D+1);
	auto p = get(1, n, A + 1, B + 1, 1, mx);
	// cout << p[0] << ' ';
	// cout << A << ' '<< B  <<'\n';
	if(p[0] == -1) return -1;
	v = p[1];

	for(int j = K - 1; j >= 0; --j){
		if(v >= C && v <= D) return ans;
		if(H[up[v][j][0]] <= mx){
			ans += (1<<j);
			v = up[v][j][0];
		}
	}
	for(int j = K - 1; j >= 0; --j){
		if(v >= C && v <= D) return ans;
		if(H[up[v][j][1]] <= mx){
			ans += (1<<j);
			v = up[v][j][1];
		}
	}
	if(v >= C && v <= D) return ans;
	return -1;
}

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:26:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |  int m = l+r>>1;
      |          ~^~
jumps.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < T[k<<1].size(); ++i){
      |                 ~~^~~~~~~~~~~~~~~~
jumps.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(p < T[k<<1|1].size() && T[k<<1|1][p] < T[k<<1][i]){
      |         ~~^~~~~~~~~~~~~~~~~~
jumps.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  while(p < T[k<<1|1].size())
      |        ~~^~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'std::array<int, 2> get(int, int, int, int, int, int)':
jumps.cpp:56:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int m = l+r>>1;
      |          ~^~

• Subtask 1: 0 / 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