Submission #400198

#	Time	Username	Problem	Language	Result	Execution time	Memory
400198		GioChkhaidze	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	214 ms	18140 KiB

railway_trip

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

const int N = 1e5 + 5;

stack < int > st;
int a[N], L[N][19], R[N][19];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n, k, q;
	cin >> n >> k >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	stack < int > st;
	st.push(0);
	a[0] = k + 1;
	for (int i = 1; i <= n; ++i) {
		while (a[st.top()] < a[i]) {
			st.pop();
		}
		L[i][0] = st.top();
		st.push(i);
	}
	
	while (st.size())	
		st.pop();
	
	st.push(n + 1);
	a[n + 1] = k + 1;
	for (int i = n; i >= 1; --i) {
		while (a[st.top()] < a[i]) {
			st.pop();
		}
		R[i][0] = st.top();
		st.push(i);
	}
	
	while (st.size())	
		st.pop();
	
	for (int i = 1; i <= n; ++i) {
		if (L[i][0] == 0) {
			L[i][0] = i;
		}
		
		if (R[i][0] == n + 1) {
			R[i][0] = i;
		}
	}
	
	for (int j = 1; j <= 17; ++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]);
		}
	}
	
	for (int i = 1; i <= q; ++i) {
		int a, b, lt, rt, l, r, c, ans = 0;
		cin >> a >> b;
		if (a > b) swap(a, b);
		
		l = r = a;
		for (int j = 17; j >= 0; --j) {
			if (max(R[l][j], R[r][j]) < b) {
				ans += (1 << j);
				lt = l, rt = r;
				l = min(L[lt][j], L[rt][j]);
				r = max(R[lt][j], R[rt][j]);
			}
		}
		
		c = r, l = r = b;
		for (int j = 17; j >= 0; --j) {
			if (c < min(L[l][j], L[r][j])) {
				ans += (1 << j);
				lt = l, rt = r;
				l = min(L[lt][j], L[rt][j]);
				r = max(R[lt][j], R[rt][j]);
			}
		}
		
		cout << ans << "\n";
	}
}

Compilation message (stderr)

railway_trip.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main () {
      |       ^

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