Submission #1188766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188766		dubabuba	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	199 ms	17088 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

const int inf = 2e9 + 10;
const int mxn = 1e5 + 10;
const int LOG = 20;

int a[mxn], n, k, q;
int L[LOG][mxn];
int R[LOG][mxn];

int main() {
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		L[0][i] = i - 1;
		R[0][i] = i + 1;
	}

	L[0][1] = 1;
	for(int i = 1; i <= n; i++) {
		while(a[i] > a[L[0][i]]) {
			L[0][i] = L[0][L[0][i]];
		}
	}

	R[0][n] = n;
	for(int i = n - 1; i > 0; i--) {
		while(a[i] > a[R[0][i]]) {
			R[0][i] = R[0][R[0][i]];
		}
	}

	// for(int i = 1; i <= n; i++)
	// 	cout << a[i] << ' ';
	// cout << endl;
	// for(int i = 1; i <= n; i++) {
	// 	cout << i << ": " << L[0][i] << ' ' << R[0][i] << endl;
	// }

	for(int k = 1; k < LOG; k++)
	for(int i = 1; i <= n; i++) {
		int x = L[k - 1][i], y = R[k - 1][i];
		L[k][i] = min(L[k - 1][x], L[k - 1][y]);
		R[k][i] = max(R[k - 1][x], R[k - 1][y]);
	}

	while(q--) {
		int mn, mx, ans = 0;
		cin >> mn >> mx;
		if(mn > mx) swap(mn, mx);

		int tar = mx;
		int l = mn, r = mn;
		for(int k = LOG - 1; k >= 0; k--) {
			int susL = min(L[k][l], L[k][r]);
			int susR = max(R[k][l], R[k][r]);

			if(susR < tar) {
				l = susL;
				r = susR;
				ans += (1 << k);
			}
		}

		// cout << l << ' ' << r << endl;

		tar = r;
		l = mx, r = mx;
		for(int k = LOG - 1; k >= 0; k--) {
			int susL = min(L[k][l], L[k][r]);
			int susR = max(R[k][l], R[k][r]);

			if(tar < susL) {
				l = susL;
				r = susR;
				ans += (1 << k);
			}
		}

		// cout << l << ' ' << r << endl;

		cout << ans << endl;
	}
	return 0;
}

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