제출 #412739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412739		errorgorn	밀림 점프 (APIO21_jumps)	C++17	100 / 100	1689 ms	72372 KiB

jumps

#include "jumps.h"

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

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

struct node{
	int s,e,m;
	int mx=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int k){
		if (s==e) mx=k;
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			
			mx=max(l->mx,r->mx);
		}
	}
	
	int query_mx(int i,int j){
		if (s==i && e==j) return mx;
		else if (j<=m) return l->query_mx(i,j);
		else if (m<i) return r->query_mx(i,j);
		else return max(l->query_mx(i,m),r->query_mx(m+1,j));
	}
} *root=new node(0,200005);

int n;
int h[200005];
//when we jump to left/right where do we go to?
int l[200005];
int r[200005];

vector<int> proc;
int tkdl[200005][20];
int tkdr[200005][20];
int tkdlr[200005][20];


void init(int N, std::vector<int> H) {
	n=N;
	rep(x,0,n) h[x]=H[x];
	
	rep(x,0,n) root->update(x,h[x]);
	
	h[n]=1e9;
	rep(x,0,n) l[x]=r[x]=n;
	
	vector<int> stk;
	rep(x,0,n){
		while (!stk.empty() && h[stk.back()]<h[x]) stk.pob();
		if (!stk.empty()) l[x]=stk.back();
		stk.pub(x);
	}
	
	stk={};
	rep(x,n,0){
		while (!stk.empty() && h[stk.back()]<h[x]) stk.pob();
		if (!stk.empty()) r[x]=stk.back();
		stk.pub(x);
	}
	
	//rep(x,0,n) cout<<l[x]<<" "; cout<<endl;
	//rep(x,0,n) cout<<r[x]<<" "; cout<<endl;
	
	memset(tkdl,-1,sizeof(tkdl));
	memset(tkdr,-1,sizeof(tkdr));
	memset(tkdlr,-1,sizeof(tkdlr));
	
	rep(x,0,n) proc.pub(x);
	sort(all(proc),[](int i,int j){
		return h[i]>h[j];
	});
	
	for (auto &it:proc){
		if (l[it]==n) continue;
		
		int curr=tkdl[it][0]=l[it];
		rep(x,0,20){
			if (curr==-1) continue;
			curr=tkdl[it][x+1]=tkdl[curr][x];
		}
	}
	
	for (auto &it:proc){
		if (r[it]==n) continue;
		
		int curr=tkdr[it][0]=r[it];
		rep(x,0,20){
			if (curr==-1) continue;
			curr=tkdr[it][x+1]=tkdr[curr][x];
		}
	}
	
	for (auto &it:proc){
		int nxt;
		if (h[l[it]]>h[r[it]]) nxt=l[it];
		else nxt=r[it];
		
		if (nxt==n) continue;
		
		int curr=tkdlr[it][0]=nxt;
		rep(x,0,20){
			if (curr==-1) continue;
			curr=tkdlr[it][x+1]=tkdlr[curr][x];
		}
	}
	
	//rep(x,0,n) cout<<tkdlr[x][0]<<" "; cout<<endl;
}

int minimum_jumps(int a, int b, int c, int d) {
	int lo,hi;
	
	if (b+1==c) lo=-1;
	else lo=root->query_mx(b+1,c-1);
	
	hi=root->query_mx(c,d);
	
	if (lo>hi) return -1;
	if (h[b]>hi) return -1;
	
	int curr=b;
	rep(x,20,0){
		//cout<<"debug: "<<curr<<" "<<x<<" "<<tkdl[curr][x]<<endl;
		if (tkdl[curr][x]!=-1 && a<=tkdl[curr][x] && h[tkdl[curr][x]]<=hi){
			curr=tkdl[curr][x];
		}
	}
	//cout<<"debug: "<<curr<<endl;
	
	int ans=0;
	
	rep(x,20,0){
		if (tkdlr[curr][x]!=-1 && h[tkdlr[curr][x]]<lo){
			//cout<<curr<<" "<<tkdlr[curr][x]<<endl;
			curr=tkdlr[curr][x];
			ans+=(1<<x);
		}
	}
	
	if (h[curr]<lo) if (tkdlr[curr][0]!=-1 && h[tkdlr[curr][0]]<=hi){
		curr=tkdlr[curr][0];
		ans++;
	}
	
	rep(x,20,0){
		if (tkdr[curr][x]!=-1 && h[tkdr[curr][x]]<lo){
			curr=tkdr[curr][x];
			ans+=(1<<x);
		}
	}
	
	if (h[curr]<lo){
		ans++;
	}
	
	return ans+1;
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In constructor 'node::node(int, int)':
jumps.cpp:26:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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