Submission #444783

#	Time	Username	Problem	Language	Result	Execution time	Memory
444783		arnold518	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4093 ms	79668 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e5;

int N;
int H[MAXN+10];

struct SEG
{
	pii tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]={H[tl], tl};
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	pii query(int node, int tl, int tr, int l, int r)
	{
		if(r<tl || tr<l) return pii(-1, -1);
		if(l<=tl && tr<=r) return tree[node];
		int mid=tl+tr>>1;
		return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
}seg;

int par[MAXN+10], root, dep[MAXN+10];

int f(int l, int r, int d)
{
	if(l>r) return -1;
	int pos=seg.query(1, 1, N, l, r).second;
	dep[pos]=d;
	int lc=f(l, pos-1, d+1), rc=f(pos+1, r, d+1);
	if(lc!=-1)
	{
		par[lc]=pos;
	}
	if(rc!=-1)
	{
		par[rc]=-pos;
	}
	return pos;
}

int L[MAXN+10], R[MAXN+10];
int spa1[MAXN+10][30], spa2[MAXN+10][30];

void init(int _N, vector<int> _H)
{
	N=_N;
	for(int i=1; i<=N; i++) H[i]=_H[i-1];
	seg.init(1, 1, N);
	root=f(1, N, 1);

	H[0]=H[N+1]=2147483647;

	vector<int> S;
	S.push_back(0);
	for(int i=1; i<=N; i++)
	{
		while(!S.empty() && H[S.back()]<H[i]) S.pop_back();
		L[i]=S.back();
		if(L[i]==0) L[i]=-1;
		S.push_back(i);
	}
	S.clear();
	S.push_back(N+1);
	for(int i=N; i>=1; i--)
	{
		while(!S.empty() && H[S.back()]<H[i]) S.pop_back();
		R[i]=S.back();
		if(R[i]==N+1) R[i]=-1;
		S.push_back(i);
	}

	//for(int i=1; i<=N; i++) printf("%d ", L[i]); printf("\n");
	//for(int i=1; i<=N; i++) printf("%d ", R[i]); printf("\n");
	//for(int i=1; i<=N; i++) printf("%d ", par[i]); printf("\n");
	//for(int i=1; i<=N; i++) printf("%d ", dep[i]); printf("\n");

	for(int i=1; i<=N; i++)
	{
		if(par[i]==0) continue;
		if(par[i]>0)
		{
			spa1[i][0]=R[i];
			spa2[i][0]=L[i];
		}
		else
		{
			spa1[i][0]=L[i];
			spa2[i][0]=R[i];
		}
	}
	for(int j=1; j<=20; j++) for(int i=1; i<=N; i++)
	{
		if(spa1[i][j-1]==-1) spa1[i][j]=-1;
		else spa1[i][j]=spa1[spa1[i][j-1]][j-1];

		if(spa2[i][j-1]==-1) spa2[i][j]=-1;
		else spa2[i][j]=spa2[spa2[i][j-1]][j-1];
	}
}

int solve(int A, int B)
{
	int now=A;
	int ans=0;
	for(int i=20; i>=0; i--)
	{
		if(spa2[now][i]==-1) continue;
		if(dep[spa2[now][i]]<dep[B]) continue;
		ans+=(1<<i);
		now=spa2[now][i];
	}
	for(int i=20; i>=0; i--)
	{
		if(spa1[now][i]==-1) continue;
		if(dep[spa1[now][i]]<dep[B]) continue;
		ans+=(1<<i);
		now=spa1[now][i];
	}
	if(now!=B) return -1;
	return ans;
}

int dist[MAXN+10];

int minimum_jumps(int A, int B, int C, int D)
{
	A++; B++; C++; D++;

	queue<int> Q;
	for(int i=1; i<=N; i++) dist[i]=-1;
	for(int i=A; i<=B; i++) dist[i]=0, Q.push(i);
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		if(C<=now && now<=D) return dist[now];
		if(L[now]!=-1)
		{
			if(dist[L[now]]==-1)
			{
				Q.push(L[now]);
				dist[L[now]]=dist[now]+1;
			}
		}
		if(R[now]!=-1)
		{
			if(dist[R[now]]==-1)
			{
				Q.push(R[now]);
				dist[R[now]]=dist[now]+1;
			}
		}
	}
	return -1;
}

Compilation message (stderr)

jumps.cpp: In member function 'void SEG::init(int, int, int)':
jumps.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid=tl+tr>>1;
      |           ~~^~~
jumps.cpp: In member function 'pii SEG::query(int, int, int, int, int)':
jumps.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=tl+tr>>1;
      |           ~~^~~

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