제출 #1311101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311101		thelegendary08	밀림 점프 (APIO21_jumps)	C++20	48 / 100	790 ms	88088 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; vector<pair<int,int>> 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]=mp(x,k-n); 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]);
	}
	pair<int,int> quermin(int l, int r){
		pair<int,int> ret = mp(4e18,-1); 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; 
	}
	pair<int,int> quermax(int l, int r){
		pair<int,int> ret = mp(-4e18,-1); 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).first; 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).first; 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]=R[i],b[i][0]=R[i]; else if(R[i]==n)a[i][0]=L[i],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]=-1; else{
				a[i][j]=a[a[i][j-1]][j-1];
			}
			if(b[i][j-1]==-1)b[i][j]=-1; else b[i][j] = b[b[i][j-1]][j-1];
		}
	}
}

signed minimum_jumps(signed A, signed  B, signed C, signed D) {
	int s, t = C; int lo = A, hi = B+1; while(lo < hi){
		int mid = lo + (hi-lo)/2; if(T.quermax(mid,B).first < h[t])hi=mid; else lo=mid+1;
	} if(lo==B+1)return -1; pair<int,int>p = T.quermax(lo,B); if(p.first > h[t])return -1; s = p.second;
	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: 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