Submission #860409

#	Time	Username	Problem	Language	Result	Execution time	Memory
860409		mychecksedad	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 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], le[N][K], ri[N][K];
vector<int> H;
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 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] = max(L[i], R[i]);
		}else{
			up[i][0][1] = max(L[i], R[i]);
			up[i][0][0] = R[i];
		}
		le[i][0] = L[i];
		ri[i][0] = R[i];
	}
	le[n][0] = n;
	ri[n][0] = n;
	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] = max(up[i][j - 1][1], up[up[i][j - 1][0]][1]);
			le[i][j] = le[le[i][j - 1]][j - 1];
			ri[i][j] = ri[ri[i][j - 1]][j - 1];
		}
	}

}
int minimum_jumps(int A, int B, int C, int D){
	int v = -1, ans = 0;
	int mx = maxx(C+1, D+1);
	
	v = B;
	for(int j = K - 1; j >= 0; --j){
		if(le[v][j] >= A && H[le[v][j]] < mx){
			v = le[v][j];
		}
	}
	if(H[v] > mx) return -1;

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

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:72:61: error: no matching function for call to 'max(int&, int [2])'
   72 |    up[i][j][1] = max(up[i][j - 1][1], up[up[i][j - 1][0]][1]);
      |                                                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from jumps.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
jumps.cpp:72:61: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'int [2]')
   72 |    up[i][j][1] = max(up[i][j - 1][1], up[up[i][j - 1][0]][1]);
      |                                                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from jumps.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
jumps.cpp:72:61: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'int [2]')
   72 |    up[i][j][1] = max(up[i][j - 1][1], up[up[i][j - 1][0]][1]);
      |                                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from jumps.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
jumps.cpp:72:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   72 |    up[i][j][1] = max(up[i][j - 1][1], up[up[i][j - 1][0]][1]);
      |                                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from jumps.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
jumps.cpp:72:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   72 |    up[i][j][1] = max(up[i][j - 1][1], up[up[i][j - 1][0]][1]);
      |                                                             ^