Submission #1228774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228774		emptypringlescan	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	91 ms	17352 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
int n,k,q;
int arr[100005];
pair<int,int> twok[20][100005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k >> q;
	for(int i=1; i<=n; i++) cin >> arr[i];
	vector<int> mono;
	for(int i=1; i<=n; i++){
		while(!mono.empty()&&arr[mono.back()]<arr[i]) mono.pop_back();
		if(mono.empty()) twok[0][i].first=1;
		else twok[0][i].first=mono.back();
		mono.push_back(i);
	}
	mono.clear();
	for(int i=n; i>0; i--){
		while(!mono.empty()&&arr[mono.back()]<arr[i]) mono.pop_back();
		if(mono.empty()) twok[0][i].second=n;
		else twok[0][i].second=mono.back();
		mono.push_back(i);
	}
	for(int i=0; i<19; i++){
		for(int j=1; j<=n; j++){
			int a=twok[i][j].first,b=twok[i][j].second;
			twok[i+1][j].first=min(twok[i][a].first,twok[i][b].first);
			twok[i+1][j].second=max(twok[i][a].second,twok[i][b].second);
		}
	}
	while(q--){
		int a,b;
		cin >> a >> b;
		if(a>b) swap(a,b);
		int ans=0;
		pair<int,int> cur={a,a};
		for(int i=19; i>=0; i--){
			pair<int,int> nxt;
			nxt.first=min(twok[i][cur.first].first,twok[i][cur.second].first);
			nxt.second=max(twok[i][cur.first].second,twok[i][cur.second].second);
			if(nxt.second<b){
				ans+=(1<<i);
				cur=nxt;
			}
		}
		int hm=cur.second;
		cur={b,b};
		for(int i=19; i>=0; i--){
			pair<int,int> nxt;
			nxt.first=min(twok[i][cur.first].first,twok[i][cur.second].first);
			nxt.second=max(twok[i][cur.first].second,twok[i][cur.second].second);
			if(nxt.first>hm){
				ans+=(1<<i);
				cur=nxt;
			}
		}
		cout << ans << '\n';
	}
}

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