Submission #692526

#	Time	Username	Problem	Language	Result	Execution time	Memory
692526		gustjwkd1007	Rainforest Jumps (APIO21_jumps)	C++17	48 / 100	1750 ms	74712 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}

int inv[210000], dep[210000];
int sparse[2][210000][30];
vector <int> input, gan[210000];
int max_seg[810000];
int n;

int build(int s, int e, int ind){
	if(s==e)
		return max_seg[ind] = input[s];
	int m = (s+e)/2;
	return max_seg[ind] = max(build(s, m, ind*2), build(m+1, e, ind*2+1));
}

int rmq(int s, int e, int ind, int x, int y){
	if(s>y||e<x)
		return 0;
	if(s>=x&&e<=y)
		return max_seg[ind];
	return max(
		rmq(s, (s+e)/2, ind*2, x, y),
		rmq((s+e)/2+1, e, ind*2+1, x, y)
	);
}

int low_cd(int C, int D, int M){
	int l = C, r = D;
	while(l<=r){
		int m = (l+r)/2;
		if(rmq(1, n, 1, C, m)>M)
			r = m-1;
		else
			l = m+1;
	}
	return l;
}

int low_ab(int A, int B, int M){
	int l = A, r = B;
	while(l<=r){
		int m = (l+r)/2;
		if(rmq(1, n, 1, m, B)<M)
			r = m-1;
		else
			l = m+1;
	}
	return l-1;
}

int dist(int s, int e){
	int re=0;
	for(int i=29;i>=0;i--)if(dep[sparse[1][s][i]]>=dep[e]){
		re += (1 << i);
		s = sparse[1][s][i];
	}
	return re - dep[e] + dep[s];
}

void set_inv(){
	for(int i=1;i<=n;i++)
		inv[input[i]]=i;
}

void dfs(int now){
	for(int t=0;t<2;t++){
		for(int i=1;i<30;i++)
			sparse[t][now][i] = sparse[t][sparse[t][now][i-1]][i-1];
	}
	for(int nex : gan[now]){
		dep[nex] = dep[now]+1;
		dfs(nex);
	}
}

void set_sparse(){
	stack <int> ms;
	ms.push(0);
	for(int i=1;i<=n;i++){
		for(;input[ms.top()]<input[i];ms.pop());
		sparse[0][i][0] = ms.top();
		ms.push(i);
	}

	while(ms.size()) ms.pop();

	ms.push(0);
	for(int i=n;i>0;i--){
		for(;input[ms.top()]<input[i];ms.pop());
		sparse[1][i][0] = ms.top();
		ms.push(i);
	}

	for(int i=1;i<=n;i++)if(input[sparse[0][i][0]]>input[sparse[1][i][0]])
		swap(sparse[0][i][0], sparse[1][i][0]);
	for(int i=1;i<=n;i++)
		gan[sparse[0][i][0]].push_back(i);

	dfs(0);
}

void init(int N, std::vector<int> H) {
	input.push_back(INF);
	input.insert(input.end(), H.begin(), H.end());
	n=N;
	set_inv();
	set_sparse();
	build(1, n, 1);
}

int minimum_jumps(int A, int B, int C, int D) {
	A++, B++, C++, D++;
	int M = rmq(1, n, 1, B+1, C-1);
	int la = low_ab(A, B, M);
	int lc = low_cd(C, D, M);
	if(lc>D)
		return -1;
	if(la<A)
		return dist(inv[rmq(1, n, 1, A, B)], lc);
	if(rmq(1, n, 1, C, D)>input[la])
		return 1;
	if(la==B)
		return -1;
	return dist(inv[rmq(1, n, 1, la+1, B)], lc);
}

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