Submission #531049

#	Time	Username	Problem	Language	Result	Execution time	Memory
531049		AdamGS	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1223 ms	66876 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7, LG=20;
int T[LIM], lewo[LIM][LG], prawo[LIM][LG], ile[LIM][LG], ma[LIM][LG], n;
void init(int N, vector<int>H) {
	n=N;
	rep(i, n) T[i+1]=H[i];
	stack<pair<int,int>>S;
	T[0]=T[n+1]=INF;
	rep(i, n+2) {
		while(!S.empty() && S.top().st<T[i]) S.pop();
		if(!S.empty()) lewo[i][0]=S.top().nd;
		else lewo[i][0]=i;
		S.push({T[i], i});
	}
	while(!S.empty()) S.pop();
	for(int i=n+1; i>=0; --i) {
		while(!S.empty() && S.top().st<T[i]) S.pop();
		if(!S.empty()) prawo[i][0]=S.top().nd;
		else prawo[i][0]=i;
		S.push({T[i], i});
	}
	for(int j=1; j<LG; ++j) rep(i, n+2) {
		lewo[i][j]=lewo[lewo[i][j-1]][j-1];
		prawo[i][j]=prawo[prawo[i][j-1]][j-1];
	}
	rep(i, n+2) {
		int p=i;
		ile[i][0]=-1;
		for(int j=LG-1; j>=0; --j) if(prawo[p][j]<prawo[lewo[i][0]][0]) {
			p=prawo[p][j];
			ile[i][0]+=1<<j;
		}
		if(ile[i][0]>0) ma[i][0]=ile[i][0];
	}
	for(int j=1; j<LG; ++j) rep(i, n+2) {
		ile[i][j]=ile[i][j-1]+ile[lewo[i][j-1]][j-1];
		ma[i][j]=max(ma[i][j-1], ile[i][j-1]+ma[lewo[i][j-1]][j-1]);
	}
}
int minimum_jumps(int a, int b, int l, int r) {
	++a; ++b; ++l; ++r;
	int p=b;
	for(int i=LG-1; i>=0; --i) if(prawo[p][i]<=r) p=prawo[p][i];
	if(p<l) return -1;
	int x=b;
	for(int i=LG-1; i>=0; --i) if(T[lewo[x][i]]<T[p] && lewo[x][i]>=a) x=lewo[x][i];
	int sum=1, y=x;
	for(int i=LG-1; i>=0; --i) if(prawo[y][i]<l) {
		y=prawo[y][i];
		sum+=1<<i;
	}
	int z=T[y], ans=0, akt=0, ans2=0;
	y=prawo[y][0];
	p=x;
	for(int i=LG-1; i>=0; --i) if(T[lewo[x][i]]<T[y]) {
		ans=max(ans, akt+ma[x][i]);
		akt+=ile[x][i];
		x=lewo[x][i];
	}
	ans=sum-ans;
	for(int i=LG-1; i>=0; --i) if(T[lewo[p][i]]<z) {
		p=lewo[p][i];
		ans2+=1<<i;
	}
	p=lewo[p][0];
	if(prawo[p][0]<=r) ans=min(ans, ans2+2);
	return ans;
}

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