제출 #1213210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213210		k1r1t0	Passport (JOI23_passport)	C++20	22 / 100	319 ms	117932 KiB

passport

#include <bits/stdc++.h>

using namespace std;

const int N = 810000;
const int LOGN = 20;

int n, l[N], r[N], fl[N], fr[N], bl[N], br[N], ans[N], tl[LOGN][N], tr[LOGN][N];
vector<pair<int, int>> g[N];

int cl(int i, int j) {
	return (l[i] < l[j] ? i : j);
}

int cr(int i, int j) {
	return (r[i] > r[j] ? i : j);
}

int gl(int l, int r) {
	if (l > r) return -1; // WTF
	int t = 31 - __builtin_clz(r - l + 1);
	return cl(tl[t][l], tl[t][r - (1 << t) + 1]);
}

int gr(int l, int r) {
	if (l > r) return -1; // WTF
	int t = 31 - __builtin_clz(r - l + 1);
	return cr(tr[t][l], tr[t][r - (1 << t) + 1]);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> l[i] >> r[i];
	for (int i = 1; i <= n; i++)
		tl[0][i] = tr[0][i] = i;
	for (int k = 1; k < LOGN; k++)
	for (int i = 1; i + (1 << k) - 1 <= n; i++) {
		tl[k][i] = cl(tl[k - 1][i], tl[k - 1][i + (1 << (k - 1))]);
		tr[k][i] = cr(tr[k - 1][i], tr[k - 1][i + (1 << (k - 1))]);
	}
	for (int i = 1; i <= n; i++) {
		fl[i] = gl(l[i], r[i]);
		fr[i] = gr(l[i], r[i]);
		bl[i] = N;
		br[i] = N;
		if (l[i] == 1) bl[i] = 0;
		if (r[i] == n) br[i] = 0;
	}
	for (int i = 1; i <= n; i++)
		bl[i] = min(bl[i], bl[fl[i]] + 1);
	for (int i = n; i >= 1; i--)
		br[i] = min(br[i], br[fr[i]] + 1);
	for (int i = 1; i <= 4 * n; i++)
		ans[i] = N;
	for (int i = 1; i <= n; i++)
	for (int lv = 0; lv <= 1; lv++)
	for (int rv = 0; rv <= 1; rv++) {
		if (lv & rv) {
			g[0].push_back({i + 3 * n, 1});
			continue;
		}
		int t = (lv + 2 * rv) * n;
		g[fl[i] + t].push_back({i + t, 1});
		g[fr[i] + t].push_back({i + t, 1});
		if (lv | rv) {
			g[i + 3 * n].push_back({i + t, lv * br[i] + rv * bl[i]});
			continue;
		}
		g[i + 1 * n].push_back({i, bl[i]});
		g[i + 2 * n].push_back({i, br[i]});
		g[i + 3 * n].push_back({i, bl[i] + br[i]});
	}
	set<pair<int, int>> st;
	st.insert({0, 0});
	while (!st.empty()) {
		auto [d, v] = *st.begin(); st.erase(st.begin());
		for (auto [u, w] : g[v]) if (d + w < ans[u]) {
			st.erase({ans[u], u});
			ans[u] = d + w;
			st.insert({ans[u], u});
		}
	}
	int q; cin >> q;
	while (q--) {
		int x; cin >> x;
		if (ans[x] >= N)
			ans[x] = -1;
		cout << ans[x] << '\n';
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46