Submission #715626

#	Time	Username	Problem	Language	Result	Execution time	Memory
715626		valerikk	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	363 ms	29780 KiB

railway_trip

#include <bits/stdc++.h>
 
using namespace std;
 
struct kek {
	int mx, l, r;
};
 
const int N = 1e5 + 7;
const int L = 19;
 
int n, k, q;
int a[N], pos[N];
int nxt[N], realnxt[N];
int prv[N], realprv[N];
kek go[L][N];
 
kek merge(const kek &a, const kek &b) {
	if (a.mx == b.mx) {
		return {a.mx, min(a.l, b.l), max(a.r, b.r)};
	}
	return a.mx > b.mx ? a : b;
}
 
kek t[2 * N];
 
kek get(int l, int r) {
	kek ret = {-1, -1, -1};
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			ret = merge(ret, t[l]);
			++l;
		}
		if (r & 1) {
			--r;
			ret = merge(ret, t[r]);
		}
	}
	return ret;
}
 
int dist(int i, int j) {
	if (i < j) {
		if (nxt[i] == j) {
			return 1;
		}
		kek lol = {a[i], i, i};
		int ret = 2;
		for (int p = L - 1; p >= 0; --p) {
			kek lol1 = merge(go[p][lol.l], go[p][lol.r]);
			lol1 = merge(lol1, lol);
			bool ok = false;
			if (lol1.mx >= a[j]) {
				ok = true;
			} else {
				if (nxt[lol1.r] == j) {
					ok = true;
				}
			}
			if (!ok) {
				ret += (1 << p);
				lol = lol1;
			}
		}
		return ret;
	}
	if (prv[i] == j) {
		return 1;
	}
	kek lol = {a[i], i, i};
	int ret = 2;
	for (int p = L - 1; p >= 0; --p) {
		kek lol1 = merge(go[p][lol.l], go[p][lol.r]);
		lol1 = merge(lol1, lol);
		bool ok = false;
		if (lol1.mx >= a[j]) {
			ok = true;
		} else {
			if (prv[lol1.l] == j) {
				ok = true;
			}
		}
		if (!ok) {
			ret += (1 << p);
			lol = lol1;
		}
	}
	return ret;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> q;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		--a[i];
	}
	for (int i = 0; i < n; ++i) {
		nxt[i] = n;
		prv[i] = -1;
		realnxt[i] = n;
		realprv[i] = -1;
	}
	{
		vector<int> st;
		for (int i = 0; i < n; ++i) {
			while (!st.empty() && a[st.back()] <= a[i]) {
				nxt[st.back()] = i;
				st.pop_back();
			}
			st.push_back(i);
		}
	}
	{
		vector<int> st;
		for (int i = 0; i < n; ++i) {
			while (!st.empty() && a[st.back()] < a[i]) {
				realnxt[st.back()] = i;
				st.pop_back();
			}
			st.push_back(i);
		}
	}
	{
		vector<int> st;
		for (int i = n - 1; i >= 0; --i) {
			while (!st.empty() && a[st.back()] <= a[i]) {
				prv[st.back()] = i;
				st.pop_back();
			}
			st.push_back(i);
		}
	}
	{
		vector<int> st;
		for (int i = n - 1; i >= 0; --i) {
			while (!st.empty() && a[st.back()] < a[i]) {
				realprv[st.back()] = i;
				st.pop_back();
			}
			st.push_back(i);
		}
	}
	{
		vector<int> cnt(k, 0);
		for (int i = 0; i < n; ++i) {
			pos[i] = cnt[a[i]];
			++cnt[a[i]];
		}
	}
	for (int i = 0; i < n; ++i) {
		t[i + n] = {a[i], i, i};
	}
	for (int i = n - 1; i > 0; --i) {
		t[i] = merge(t[2 * i], t[2 * i + 1]);
	}
	for (int i = 0; i < n; ++i) {
		go[0][i] = {a[i], i, i};
		if (prv[i] != -1) {
			go[0][i] = merge(go[0][i], {a[prv[i]], prv[i], prv[i]});
		}
		if (nxt[i] != n) {
			go[0][i] = merge(go[0][i], {a[nxt[i]], nxt[i], nxt[i]});
		}
	}
	for (int p = 1; p < L; ++p) {
		for (int i = 0; i < n; ++i) {
			go[p][i] = go[p - 1][i];
			go[p][i] = merge(go[p][i], go[p - 1][go[p - 1][i].l]);
			go[p][i] = merge(go[p][i], go[p - 1][go[p - 1][i].r]);
		}
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		--l;
		--r;
		if (l > r) {
			swap(l, r);
		}
		auto lol = get(l + 1, r);
		if (lol.mx < min(a[l], a[r])) {
			cout << "0\n";
			continue;
		}
		int ans = 1e9;
		if (lol.mx < a[l]) {
			ans = min(ans, dist(r, l));
		}
		if (lol.mx < a[r]) {
			ans = min(ans, dist(l, r));
		}
		ans = min(ans, dist(l, lol.l) + dist(r, lol.r) + pos[lol.r] - pos[lol.l]);
		if (realprv[lol.l] != -1) {
			ans = min(ans, dist(l, realprv[lol.l]) + dist(r, realprv[lol.l]));
		}
		cout << ans - 1 << "\n";
	}
	return 0;
}

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