제출 #411908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411908		alishahali1382	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	1303 ms	32064 KiB

railway_trip

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=17;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], L[MAXN], R[MAXN];
pii SP[LOG][MAXN];
int L2[LOG][MAXN], R2[LOG][MAXN];
pii seg[MAXN<<1];

pii Get(int l, int r){
	pii res=seg[0];
	for (l+=n, r+=n; l<r; l>>=1, r>>=1){
		if (l&1) res=max(res, seg[l++]);
		if (r&1) res=max(res, seg[--r]);
	}
	return res;
}
pii combine(pii i, pii j){ return {min(i.first, j.first), max(i.second, j.second)};}
int Go(int x, int y){
	if (x==y) return 0;
	if (Get(min(x, y), max(x, y)+1).first>A[y] || min(x, y)==0 || max(x, y)==n+1) return inf;
	// A[x]<=A[y]
	pii p={x, x};
	int ans=0;
	for (int i=LOG-1; ~i; i--){
		pii q=combine(SP[i][p.first], SP[i][p.second]);
		if (A[q.first]>A[y] || A[q.second]>A[y]) continue ;
		if (y<q.first || q.second<y){
			p=q;
			ans+=(1<<i);
		}
	}
//	debugp(p)
//	debug(ans)
	if (A[p.second]>A[p.first]) x=p.second;
	else if (A[p.second]<A[p.first]) x=p.first;
	else{
		if (x<y) x=p.second;
		else x=p.first;
	}
	if (x<y){
		for (int i=LOG-1; ~i; i--) if (R2[i][x]<y){
			x=R2[i][x];
			ans+=(1<<i);
		}
	}
	if (x>y){
		for (int i=LOG-1; ~i; i--) if (L2[i][x]>y){
			x=L2[i][x];
			ans+=(1<<i);
		}
	}
	return ans+1;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k>>m;
	for (int i=1; i<=n; i++) cin>>A[i];
	for (int i=1; i<=n; i++) for (L[i]=i-1; L[i] && A[L[i]]<A[i]; L[i]=L[L[i]]);
	for (int i=n; i; i--) for (R[i]=i+1; R[i]<=n && A[R[i]]<A[i]; R[i]=R[R[i]]);
	for (int i=1; i<=n; i++) seg[i+n]={A[i], i};
	for (int i=n-1; i; i--) seg[i]=max(seg[i<<1], seg[i<<1 | 1]);
	
	R[n+1]=n+1;
	for (int i=0; i<=n+1; i++){
		SP[0][i]={L[i], R[i]};
		L2[0][i]=L[i];
		R2[0][i]=R[i];
	}
	for (int j=1; j<LOG; j++) for (int i=0; i<=n+1; i++){
		int x=SP[j-1][i].first, y=SP[j-1][i].second;
		SP[j][i]=combine(SP[j-1][x], SP[j-1][y]);
		L2[j][i]=L2[j-1][L2[j-1][i]];
		R2[j][i]=R2[j-1][R2[j-1][i]];
	}
	A[0]=A[n+1]=k+1;
	
//	debug(Go(2, 7))
//	debug(Go(8, 7))
//	return 0;
	
	
	while (m--){
		cin>>x>>y;
		if (x>y) swap(x, y);
		
		int mx=Get(x, y+1).second, z=mx;
		ans=Go(x, z)+Go(y, z);
		
		z=x;
		for (int i=LOG-1; ~i; i--) if (A[L2[i][z]]<A[y]) z=L2[i][z];
		z=L[z];
//		while (z){
			ans=min(ans, Go(x, z)+Go(y, z));
//			z=L[z];
//		}
		
		z=y;
		for (int i=LOG-1; ~i; i--) if (A[R2[i][z]]<A[x]) z=R2[i][z];
		z=R[z];
//		while (z<=n){
			ans=min(ans, Go(x, z)+Go(y, z));
//			z=R[z];
//		}

		z=mx;
		for (int i=LOG-1; ~i; i--) if (R2[i][z]<=y || A[R2[i][z]]==A[mx]) z=R2[i][z];
		z=R[z];
		ans=min(ans, Go(x, z)+Go(y, z));
		
		z=mx;
		for (int i=LOG-1; ~i; i--) if (x<=L2[i][z] || A[L2[i][z]]==A[mx]) z=L2[i][z];
		z=L[z];
		ans=min(ans, Go(x, z)+Go(y, z));
		
		
		cout<<ans-1<<"\n";
	}
	
	return 0;
}
/*
15 15 1
15 6 14 8 1 9 13 3 5 10 3 2 10 3 15 
12 4

15 15 1
15 2 13 3 14 3 3 13 4 13 6 3 13 4 15 
6 12

*/

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