제출 #1310896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310896		thelegendary08	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	468 ms	75560 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 2e5 + 5; 
const int lg = 18;
int n; vi h; int a[mxn][lg], b[mxn][lg], L[mxn], R[mxn]; 
struct segtree{
	int n; vi mx, mn; 
	segtree(){}
	segtree(int x){
		n=x; mx.resize(2*n+5); mn.resize(2*n+5); 
	}
	void update(int k, int x){
		k+=n;mn[k]=mx[k]=x; for(k/=2;k>=1;k/=2)mn[k]=min(mn[k*2],mn[k*2+1]),mx[k]=max(mx[k*2],mx[k*2+1]);
	}
	int quermin(int l, int r){
		int ret = 4e18; l+=n;r+=n; while(l<=r){
			if(l%2)ret=min(ret,mn[l++]); if(r%2==0)ret=min(ret,mn[r--]); l/=2; r/=2;
		} return ret; 
	}
	int quermax(int l, int r){
		int ret = -4e18; l+=n;r+=n; while(l<=r){
			if(l%2)ret=max(ret,mx[l++]); if(r%2==0)ret=max(ret,mx[r--]); l/=2; r/=2;
		} return ret; 
	}
} T;
void init(signed N, std::vector<signed> H) {
	n=N; h.resize(n); f0r(i,n)h[i]=H[i]; segtree S = segtree(n+1); FOR(i,1,n+1)S.update(i,-1); f0r(i,n){
		L[i] = S.quermax(h[i],n); S.update(h[i],i);
	} FOR(i,1,n+1)S.update(i,n); for(int i = n-1; i >= 0; i--){
		R[i] = S.quermin(h[i],n); S.update(h[i],i);
	} 
	T = segtree(n); f0r(i,n)T.update(i,h[i]); f0r(i,n){
		if(L[i]==-1&&R[i]==n)a[i][0]=b[i][0]=-1; else if(L[i]==-1)a[i][0]=b[i][0]=R[i]; else if(R[i]==n)a[i][0]=b[i][0]=L[i]; 
		else if(h[L[i]]>h[R[i]])a[i][0]=L[i],b[i][0]=R[i]; else a[i][0]=R[i],b[i][0]=L[i];
	}
	FOR(j,1,lg){
		f0r(i,n){
			if(a[i][j-1]==-1)a[i][j]=b[i][j]=-1; else{
				a[i][j]=a[a[i][j-1]][j-1], b[i][j]=b[b[i][j-1]][j-1];
			}
		}
	}
}

signed minimum_jumps(signed A, signed B, signed C, signed D) {
	int s = A, t = C; if(T.quermax(s,t-1) > h[t])return -1; 
	int ans = 0, cur = s; for(int i = lg-1; i>=0; i--){
		if(a[cur][i]!=-1&&h[a[cur][i]]<=h[t]){ans+=(1<<i),cur=a[cur][i];}
	}
	for(int i = lg-1; i>=0; i--){
		if(b[cur][i]!=-1&&h[b[cur][i]]<=h[t])ans+=(1<<i),cur=b[cur][i];
	} if(cur!=t)return -1; return ans;
}

• Subtask 1: 0 / 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