Submission #491480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
491480	2021-12-02T16:30:57 Z	SeDunion	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 KB

jumps

#include "jumps.h"

#include <vector>
#include <iostream>
#include <math.h>
#include <stack>
#include <cassert>

#define cerr if(false)cerr

using namespace std;

const int LOG = 20;

int pl[int(3e5)], pr[int(3e5)];

int high[int(3e5)][LOG], low[int(3e5)][LOG];

int canR[int(3e5)][LOG], lowR[int(3e5)][LOG];

int H[int(3e5)], id[int(3e5)];

int spmx[int(3e5)][LOG];

int lg[int(3e5)];

int getmax(int l, int r) {
	int j = lg[r - l + 1];
	return max(spmx[l][j], spmx[r - (1 << j) + 1][j]);
}

void init(int N, vector<int> a) {
	for (int &i : a) i--;
	for (int i = 0 ; i < N ; ++ i) H[i] = a[i];
	H[N] = N;
	for (int i = 0 ; i <= N ; ++ i) id[H[i]] = i;
	//id[N] = 0;
	stack<int>st;
	for (int i = 0 ; i < N ; ++ i) {
		while (st.size() && H[st.top()] < H[i]) st.pop();
		pl[H[i]] = st.size() ? H[st.top()] : N;
		st.push(i);
	}
	while (st.size()) st.pop();
	for (int i = N - 1 ; i >= 0 ; -- i) {
		while (st.size() && H[st.top()] < H[i]) st.pop();
		pr[H[i]] = st.size() ? H[st.top()] : N;
		st.push(i);
	}
	pl[N] = pr[N] = N;
	for (int i = 0 ; i <= N ; ++ i) {
		high[i][0] = max(pl[i], pr[i]);
		low[i][0] = pr[i];
		lowR[i][0] = id[pr[i]];
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i <= N ; ++ i) {
			{
				int where = high[i][j - 1];
				high[i][j] = high[where][j - 1];
				//canR[i][j] = max(canR[i][j - 1], canR[where][j - 1]);
			}
			{
				int where = low[i][j - 1];
				low[i][j] = low[where][j - 1];
				lowR[i][j] = id[low[i][j]];
			}
		}
	}
	for (int i = 0 ; i <= N ; ++ i) {
		//canR[i][0] = max({id[i], id[pr[i]], id[pl[i]]});
		canR[i][0] = max({id[i], id[pr[i]]});
		int cur = i;
		for (int j = 1 ; j < LOG ; ++ j) {
			cur = high[cur][j - 1];
			//canR[i][j] = max({id[cur], id[pr[cur]], id[pl[cur]]});
			canR[i][j] = max({id[cur], id[pr[cur]]});
		}
	}
	for (int j = 0 ; j < 2 ; ++ j) {
		for (int i = 0 ; i <= N ; ++ i) {
			cerr << canR[H[i]][j] << " \n"[i == N];
		}
	}
	cerr << "\n\n";
	for (int i = 0 ; i <= N ; ++ i) {
		spmx[i][0] = H[i];
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i + (1 << j) - 1 <= N ; ++ i) {
			spmx[i][j] = max(spmx[i][j - 1], spmx[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 2 ; i < int(3e5) ; ++ i) lg[i] = lg[i >> 1] + 1;
}

int minimum_jumps(int A, int B, int C, int D) {
	int dmx = getmax(C, D);
	int s = -1;
	{
		int l = A, r = B;
		while (l <= r) {
			int m = (l + r) >> 1;
			if (getmax(m, B) <= dmx) s = getmax(m, B), r = m - 1;
			else l = m + 1;
		}
	}
	if (s == -1) return -1;
	int ans = 0;
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (high[s][i] <= dmx && canR[s][i] < C) {
			ans += 1 << i;
			s = high[s][i];
		}
	}
	cerr << s << " s\n";
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (low[s][i] <= dmx && lowR[s][i] < C) {
			ans += 1 << i;
			s = low[s][i];
		}
	}
	cerr << s << " s\n";
	s = low[s][0], ans++;
	cerr << s << " s\n";
	cerr << "\n";
	if (id[s] < C || id[s] > D) return -1;
	return ans;
}

Compilation message

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:72:38: error: no matching function for call to 'max(<brace-enclosed initializer list>)'
   72 |   canR[i][0] = max({id[i], id[pr[i]]});
      |                                      ^
In file included from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:1:
/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:38: note:   candidate expects 2 arguments, 1 provided
   72 |   canR[i][0] = max({id[i], id[pr[i]]});
      |                                      ^
In file included from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:1:
/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:38: note:   candidate expects 3 arguments, 1 provided
   72 |   canR[i][0] = max({id[i], id[pr[i]]});
      |                                      ^
jumps.cpp:77:43: error: no matching function for call to 'max(<brace-enclosed initializer list>)'
   77 |    canR[i][j] = max({id[cur], id[pr[cur]]});
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:1:
/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:77:43: note:   candidate expects 2 arguments, 1 provided
   77 |    canR[i][j] = max({id[cur], id[pr[cur]]});
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:1:
/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:77:43: note:   candidate expects 3 arguments, 1 provided
   77 |    canR[i][j] = max({id[cur], id[pr[cur]]});
      |                                           ^