Submission #1231074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231074		duckindog	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	84 ms	14920 KiB

railway_trip

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, k, q;
int l[N];

const int LG = 16;
int L[N][LG + 1], R[N][LG + 1];

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k >> q;
	for (int i = 1; i <= n; ++i) cin >> l[i];
	
	{ // RMQ
		{ // left
			stack<int> st;
			for (int i = 1; i <= n; ++i) { 
				while (st.size() && l[st.top()] < l[i]) st.pop();
				L[i][0] = (!st.size() ? 1 : st.top());
				st.push(i);
			}
		}
		{ // right
			stack<int> st;
			for (int i = n; i >= 1; --i) { 
				while (st.size() && l[st.top()] < l[i]) st.pop();
				R[i][0] = (!st.size() ? n : st.top());
				st.push(i);
			}
		}
		for (int j = 1; j <= LG; ++j) { 
			for (int i = 1; i <= n; ++i) { 
				L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]);
				R[i][j] = max(R[L[i][j - 1]][j - 1], R[R[i][j - 1]][j - 1]);
			}
		}
	}

	while (q--) { 
		int a, b; cin >> a >> b;
		if (a > b) swap(a, b);

		int answer = 0;

		int l = a, r = a;
		for (int i = LG; i >= 0; --i) { 
			if (max(R[l][i], R[r][i]) < b) { 
				tie(l, r) = make_pair(min(L[l][i], L[r][i]), max(R[l][i], R[r][i]));
				answer += (1 << i);
			}
		}
		
		int preR = r;
		l = b, r = b;
		for (int i = LG; i >= 0; --i) { 
			if (min(L[l][i], L[r][i]) > preR) { 
				tie(l, r) = make_pair(min(L[l][i], L[r][i]), max(R[l][i], R[r][i]));
				answer += (1 << i);
			}
		}

		cout << answer << "\n";
	}
}

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