Submission #1226984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226984		siewjh	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	86 ms	15956 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int arr[MAXN], lj[MAXN][18], rj[MAXN][18];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, K, Q; cin >> N >> K >> Q;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	vector<int> st;
	for (int i = 1; i <= N; i++){
		while (!st.empty() && arr[st.back()] < arr[i]) st.pop_back();
		lj[i][0] = (st.empty() ? 1 : st.back());
		st.push_back(i);
	}
	st.clear();
	for (int i = N; i >= 1; i--){
		while (!st.empty() && arr[st.back()] < arr[i]) st.pop_back();
		rj[i][0] = (st.empty() ? N : st.back());
		st.push_back(i);
	}
	for (int k = 1; k <= 17; k++)
		for (int i = 1; i <= N; i++){
			int pl = lj[i][k - 1], pr = rj[i][k - 1];
			lj[i][k] = min(lj[pl][k - 1], lj[pr][k - 1]);
			rj[i][k] = max(rj[pl][k - 1], rj[pr][k - 1]);
		}
	while (Q--){
		int le, re, ans = 0; cin >> le >> re;
		if (le > re) swap(le, re);
		int l = le, r = le;
		for (int k = 17; k >= 0; k--){
			int nl = min(lj[l][k], lj[r][k]), nr = max(rj[l][k], rj[r][k]);
			if (nr < re){
				ans += (1 << k); l = nl, r = nr;
			}
		}
		int targ = r;
		l = re; r = re;
		for (int k = 17; k >= 0; k--){
			int nl = min(lj[l][k], lj[r][k]), nr = max(rj[l][k], rj[r][k]);
			if (nl > targ){
				ans += (1 << k); l = nl, r = nr;
			}
		}
		cout << ans << '\n';
	}
}

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