oj.uz

Submission #715626

# Submission time Handle Problem Language Result Execution time Memory
715626 2023-03-27T10:37:28 Z valerikk Railway Trip (JOI17_railway_trip) C++17
100 / 100
 363 ms 29780 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 36 ms 27552 KB Output is correct
3 Correct 36 ms 27592 KB Output is correct
4 Correct 34 ms 27584 KB Output is correct
5 Correct 36 ms 27588 KB Output is correct
6 Correct 34 ms 27596 KB Output is correct
7 Correct 36 ms 27832 KB Output is correct
8 Correct 34 ms 27780 KB Output is correct
9 Correct 33 ms 28016 KB Output is correct
10 Correct 29 ms 27808 KB Output is correct
11 Correct 34 ms 28000 KB Output is correct
12 Correct 34 ms 27960 KB Output is correct
13 Correct 37 ms 27944 KB Output is correct
14 Correct 35 ms 27980 KB Output is correct
15 Correct 46 ms 27972 KB Output is correct
16 Correct 42 ms 27936 KB Output is correct
17 Correct 34 ms 27904 KB Output is correct
18 Correct 34 ms 27816 KB Output is correct
19 Correct 31 ms 27844 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 27904 KB Output is correct
2 Correct 195 ms 27852 KB Output is correct
3 Correct 184 ms 29216 KB Output is correct
4 Correct 190 ms 29188 KB Output is correct
5 Correct 203 ms 29152 KB Output is correct
6 Correct 195 ms 29204 KB Output is correct
7 Correct 254 ms 29148 KB Output is correct
8 Correct 121 ms 29352 KB Output is correct
9 Correct 339 ms 29380 KB Output is correct
10 Correct 345 ms 29368 KB Output is correct
11 Correct 355 ms 29284 KB Output is correct
12 Correct 360 ms 29300 KB Output is correct
13 Correct 363 ms 29352 KB Output is correct
14 Correct 299 ms 29260 KB Output is correct
15 Correct 245 ms 29108 KB Output is correct
16 Correct 227 ms 29172 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 27600 KB Output is correct
2 Correct 244 ms 29364 KB Output is correct
3 Correct 228 ms 29460 KB Output is correct
4 Correct 237 ms 29352 KB Output is correct
5 Correct 355 ms 29752 KB Output is correct
6 Correct 314 ms 29624 KB Output is correct
7 Correct 329 ms 29780 KB Output is correct
8 Correct 336 ms 29488 KB Output is correct
9 Correct 295 ms 29740 KB Output is correct
10 Correct 285 ms 29684 KB Output is correct
11 Correct 306 ms 29652 KB Output is correct
12 Correct 299 ms 29692 KB Output is correct
13 Correct 327 ms 29712 KB Output is correct
14 Correct 306 ms 29732 KB Output is correct
15 Correct 328 ms 29628 KB Output is correct
16 Correct 309 ms 29768 KB Output is correct
17 Correct 244 ms 29696 KB Output is correct
18 Correct 268 ms 29648 KB Output is correct
19 Correct 257 ms 29608 KB Output is correct
20 Correct 231 ms 29380 KB Output is correct
21 Correct 251 ms 29268 KB Output is correct
22 Correct 255 ms 29292 KB Output is correct
23 Correct 245 ms 29408 KB Output is correct