oj.uz

Submission #201340

# Submission time Handle Problem Language Result Execution time Memory
201340 2020-02-10T08:31:53 Z maruii Railway Trip (JOI17_railway_trip) C++14
100 / 100
 458 ms 107624 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5496 KB Output is correct
2 Correct 8 ms 5496 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 8 ms 5496 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 7 ms 5496 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6392 KB Output is correct
2 Correct 122 ms 90092 KB Output is correct
3 Correct 135 ms 96136 KB Output is correct
4 Correct 144 ms 100968 KB Output is correct
5 Correct 142 ms 102632 KB Output is correct
6 Correct 137 ms 105068 KB Output is correct
7 Correct 139 ms 105448 KB Output is correct
8 Correct 87 ms 55404 KB Output is correct
9 Correct 111 ms 71912 KB Output is correct
10 Correct 93 ms 65260 KB Output is correct
11 Correct 134 ms 75624 KB Output is correct
12 Correct 135 ms 75752 KB Output is correct
13 Correct 141 ms 75432 KB Output is correct
14 Correct 133 ms 75496 KB Output is correct
15 Correct 133 ms 75648 KB Output is correct
16 Correct 140 ms 75908 KB Output is correct
17 Correct 162 ms 105448 KB Output is correct
18 Correct 155 ms 105452 KB Output is correct
19 Correct 158 ms 105448 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 94780 KB Output is correct
2 Correct 307 ms 92132 KB Output is correct
3 Correct 311 ms 95684 KB Output is correct
4 Correct 307 ms 96232 KB Output is correct
5 Correct 315 ms 96744 KB Output is correct
6 Correct 311 ms 97512 KB Output is correct
7 Correct 316 ms 97732 KB Output is correct
8 Correct 243 ms 69104 KB Output is correct
9 Correct 223 ms 57332 KB Output is correct
10 Correct 220 ms 57072 KB Output is correct
11 Correct 224 ms 57252 KB Output is correct
12 Correct 226 ms 57072 KB Output is correct
13 Correct 222 ms 57072 KB Output is correct
14 Correct 206 ms 56772 KB Output is correct
15 Correct 222 ms 57708 KB Output is correct
16 Correct 277 ms 66476 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 106088 KB Output is correct
2 Correct 349 ms 106984 KB Output is correct
3 Correct 325 ms 106904 KB Output is correct
4 Correct 330 ms 106860 KB Output is correct
5 Correct 219 ms 57068 KB Output is correct
6 Correct 363 ms 73580 KB Output is correct
7 Correct 358 ms 73576 KB Output is correct
8 Correct 314 ms 66996 KB Output is correct
9 Correct 377 ms 77416 KB Output is correct
10 Correct 380 ms 77288 KB Output is correct
11 Correct 402 ms 77160 KB Output is correct
12 Correct 377 ms 77160 KB Output is correct
13 Correct 380 ms 77300 KB Output is correct
14 Correct 418 ms 92008 KB Output is correct
15 Correct 431 ms 98152 KB Output is correct
16 Correct 458 ms 107624 KB Output is correct
17 Correct 401 ms 88040 KB Output is correct
18 Correct 417 ms 88168 KB Output is correct
19 Correct 402 ms 88020 KB Output is correct
20 Correct 366 ms 87672 KB Output is correct
21 Correct 325 ms 106856 KB Output is correct
22 Correct 315 ms 106880 KB Output is correct
23 Correct 352 ms 106796 KB Output is correct