제출 #116683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116683		jangwonyoung	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	281 ms	7928 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;
const int lg=4;
typedef pair<int,int> pii;
int n,k,q;
int a[100001];
int l[100001],r[100001];
int sl[18][100001],sr[18][100001];
int find(int id,int val){
	if(val==id) return 0;
	int x=0;
	int bl=id,br=id,nl,nr;
	for(int i=lg; i>=0 ;i--){
		x|=(1<<i);
		nl=min(sl[i][bl],sl[i][br]);
		nr=max(sr[i][bl],sr[i][br]);
		if(nl<=val && val<=nr) x^=(1<<i);
		else bl=nl,br=nr;
	}
	x++;
	nl=min(sl[0][bl],sl[0][br]);
	nr=max(sr[0][bl],sr[0][br]);
	if(nl==val || nr==val) return x;
	else return 1e9;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> q;
	for(int i=1; i<=n ;i++) cin >> a[i];
	stack<int>s;
	for(int i=1; i<=n ;i++){
		while(!s.empty() && a[s.top()]<a[i]) s.pop();
		if(!s.empty()) l[i]=s.top();
		else l[i]=i;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=n; i>=1 ;i--){
		while(!s.empty() && a[s.top()]<a[i]) s.pop();
		if(!s.empty()) r[i]=s.top();
		else r[i]=i;
		s.push(i);
	}
	for(int i=1; i<=n ;i++){
		sl[0][i]=l[i];sr[0][i]=r[i];
	}
	for(int j=1; j<=lg ;j++){
		for(int i=1; i<=n ;i++){
			sl[j][i]=min(sl[j-1][sl[j-1][i]],sl[j-1][sr[j-1][i]]);
			sr[j][i]=max(sr[j-1][sl[j-1][i]],sr[j-1][sr[j-1][i]]);
		}
	}
	for(int i=1; i<=q ;i++){
		int u,v;cin >> u >> v;
		if(u>v) swap(u,v);
		if(l[v]==u || r[u]==v){
			cout << "0\n";
			continue;
		}
		int x=0,y,ans=1e9;
		int bl=u,br=u,nl,nr;
		for(int j=lg; j>=0 ;j--){
			x|=(1<<j);
			nl=min(sl[j][bl],sl[j][br]);
			nr=max(sr[j][bl],sr[j][br]);
			y=find(v,nl);
			if(y==1e9) bl=nl,br=nr;
			else x^=(1<<j);
		}
		x++;
		nl=min(sl[0][bl],sl[0][br]);
		nr=max(sr[0][bl],sr[0][br]);
		y=find(v,nl);
		ans=min(ans,x+y);
		x=0,bl=u,br=u;
		for(int j=lg; j>=0 ;j--){
			x|=(1<<j);
			nl=min(sl[j][bl],sl[j][br]);
			nr=max(sr[j][bl],sr[j][br]);
			y=find(v,nr);
			if(y==1e9) bl=nl,br=nr;
			else x^=(1<<j);
		}
		x++;
		nl=min(sl[0][bl],sl[0][br]);
		nr=max(sr[0][bl],sr[0][br]);
		y=find(v,nr);
		ans=min(ans,x+y);
		cout << ans-1 << '\n';
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55