Submission #421156

#	Time	Username	Problem	Language	Result	Execution time	Memory
421156		Jasiekstrz	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	4003 ms	240064 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=2e5;
const int PP=27e4;
const int L=18;
int n;
int tab[NN+10];
int e[NN+10][2];
int jb[NN+10][L+2];
int js[NN+10][L+2];
int pot;
set<pair<int,int>> tree[2*PP+10];
void upd_ans(int &ans,int i,int c)
{
	auto it=tree[i].upper_bound({c,n+10});
	if(it!=tree[i].begin() && (ans==-1 || prev(it)->fi>tab[ans]))
		ans=prev(it)->se;
	return;
}
int read_t(int l,int r,int c) // largest <=c
{
	int ans=-1;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			upd_ans(ans,l++,c);
		if(r%2==0)
			upd_ans(ans,r--,c);
	}
	return ans;
}
void init(int N,vector<int> H)
{
	n=N;
	tab[0]=tab[N+1]=N+10;
	e[0][0]=e[0][1]=0;
	e[N+1][0]=e[N+1][1]=N+1;
	for(int i=0;i<N;i++)
		tab[i+1]=H[i];
	vector<int> st;
	st={0};
	for(int i=1;i<=N;i++)
	{
		while(tab[st.back()]<tab[i])
		{
			e[st.back()][1]=i;
			st.pop_back();
		}
		e[i][0]=st.back();
		st.push_back(i);
	}
	while(st.size()>1)
	{
		e[st.back()][1]=N+1;
		st.pop_back();
	}
	for(int i=0;i<=N+1;i++)
	{
		if(tab[e[i][0]]>tab[e[i][1]])
			swap(e[i][0],e[i][1]);
		js[i][0]=e[i][0];
		jb[i][0]=e[i][1];
	}
	for(int l=1;l<=L;l++)
	{
		for(int i=0;i<=N+1;i++)
		{
			js[i][l]=js[js[i][l-1]][l-1];
			jb[i][l]=jb[jb[i][l-1]][l-1];
		}
	}
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=N;i++)
	{
		for(int j=i+pot-1;j>0;j/=2)
			tree[j].insert({tab[i],i});
	}
	return;
}
int minimum_jumps(int A,int B,int C,int D)
{
	A++;B++;C++;D++;
	int mx2g=read_t(C,D,n+10);
	int mx2=tab[mx2g];
	int x=read_t(A,B,mx2);
	if(x==-1)
		return -1;
	int ans=0;
#warning C==D
	for(int l=L;l>=0;l--)
	{
		if(tab[jb[x][l]]<=tab[C])
		{
			x=jb[x][l];
			ans+=(1<<l);
		}
	}
	for(int l=L;l>=0;l--)
	{
		if(tab[js[x][l]]<=tab[C])
		{
			x=js[x][l];
			ans+=(1<<l);
		}
	}
	if(x<C || D<x)
		return -1;
	return ans;
}

Compilation message (stderr)

jumps.cpp:92:2: warning: #warning C==D [-Wcpp]
   92 | #warning C==D
      |  ^~~~~~~

• 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