Submission #201340

#	Time	Username	Problem	Language	Result	Execution time	Memory
201340		maruii	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	458 ms	107624 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MX = 1e5 + 5;

int N, K, Q, A[MX], stk[MX], stn, par[19][6 * MX], dst[19][6 * MX], dep[6 * MX], L[MX], R[MX], idx[6 * MX];
vector<int> edge[2 * MX];
vector<pii> itv;
int lft(int x) { return 3 * x; }
int mid(int x) { return 3 * x + 1; }
int rht(int x) { return 3 * x + 2; }
void add_par(int x, int p, int a, int b, int i) {
	idx[x] = i;
	if (a < b) par[0][x] = lft(p);
	else if (a > b) par[0][x] = rht(p);
	else par[0][x] = mid(p);
	dst[0][x] = min(a, b);
	dep[x] = dep[par[0][x]] + 1;
	for (int i = 1; i < 19; ++i) {
		par[i][x] = par[i - 1][par[i - 1][x]];
		dst[i][x] = dst[i - 1][x] + dst[i - 1][par[i - 1][x]];
	}
}

int qry(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int ret = 0;
	for (int i = 0; i < 19; ++i) if ((dep[x] - dep[y] >> i) & 1) {
		ret += dst[i][x];
		x = par[i][x];
	}
	for (int i = 18; i >= 0; --i) if (par[i][x] / 3 != par[i][y] / 3) {
		ret += dst[i][x] + dst[i][y];
		x = par[i][x], y = par[i][y];
	}
	if (idx[x] > idx[y]) swap(x, y);
	int a = x % 3, b = y % 3;
	int ret2 = ret + max(0, idx[y] - (b != 2) - idx[x] + (a == 0));
	if (par[0][x] < 3) return ret2;
	ret += dst[0][x] + dst[0][y];
	x = par[0][x], y = par[0][y];
	a = x % 3, b = y % 3;
	if (a == 1 || b == 1 || a + b != 2) return min(ret, ret2);
	return min(ret + 1, ret2);
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	itv.emplace_back(0, 1e9);
	cin >> N >> K >> Q;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	for (int i = 1; i <= N; ++i) {
		while (stn && A[stk[stn - 1]] < A[i]) {
			stn--;
			itv.emplace_back(stk[stn], i - 1);
		}
		if (stn) itv.emplace_back(stk[stn - 1], i - 1);
		if (stn && A[i] == A[stk[stn - 1]]) stn--;
		stk[stn++] = i;
	}
	sort(itv.begin(), itv.end(), [&](pii a, pii b) {
		if (a.ff == b.ff) return a.ss > b.ss;
		return a.ff < b.ff;
	});
	stn = 0;
	for (int i = 0; i < itv.size(); ++i) {
		while (stn && itv[stk[stn - 1]].ss < itv[i].ff) --stn;
		if (stn) edge[stk[stn - 1]].push_back(i);
		stk[stn++] = i;
	}
	for (int i = 0; i < itv.size(); ++i) {
		int c = edge[i].size(), k = 0;
		for (auto j : edge[i]) {
			++k;
			int p = k - 1, q = c - k;
			add_par(lft(j), i, p, q + 1, k);
			add_par(mid(j), i, p, q, k);
			add_par(rht(j), i, p + 1, q, k);
			if (itv[j].ff == itv[j].ss) {
				L[itv[j].ff] = lft(j);
				R[itv[j].ff + 1] = rht(j);
			}
		}
	}
	while (Q--) {
		int x, y; cin >> x >> y;
		if (x > y) swap(x, y);
		printf("%d\n", qry(L[x], R[y]) - 1);
	}
	return 0;
}

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