Submission #1004296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004296		Tob	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	78 ms	16700 KiB

railway_trip

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7, lg = 17;

int n, k, q;
int a[N], l[N][lg+1], r[N][lg+1];

int main () {
	FIO;
	cin >> n >> k >> q;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	stack <int> st;
	st.push(0);
	for (int i = 1; i < n; i++) {
		while (!st.empty() && a[st.top()] <= a[i]) {r[st.top()][0] = i; st.pop();}
		st.push(i);
	}
	r[n-1][0] = n-1;
	st.pop();
	st.push(n-1);
	for (int i = n-2; i >= 0; i--) {
		while (!st.empty() && a[st.top()] <= a[i]) {l[st.top()][0] = i; st.pop();}
		st.push(i);
	}
	
	for (int j = 1; j <= lg; j++) {
		for (int i = 0; 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[r[i][j-1]][j-1], r[l[i][j-1]][j-1]);
		}
	}
	
	while (q--) {
		int x, y; cin >> x >> y; x--; y--; if (x > y) swap(x, y);
		int cnt = 0, lo = x, hi = x;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nhi >= y) continue;
			lo = nlo; hi = nhi;
			cnt += (1 << i);
		}
		int nx1 = hi, nx2 = r[hi][0];
		if (nx2 == y) {
			cout << cnt << "\n";
			continue;
		}
		int cnt2 = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nlo <= nx1) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		int re = cnt+cnt2;
		cnt2 = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nhi >= nx2) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		
		re = min(re, cnt+cnt2+1);
		cnt = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nlo <= x) continue;
			lo = nlo; hi = nhi;
			cnt += (1 << i);
		}
		int ny = l[lo][0];
		cnt2 = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nlo <= ny) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		re = min(re, cnt+cnt2+1);
		cout << re << "\n";
	}

	return 0;
}

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