Submission #1210079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210079		duckindog	Passport (JOI23_passport)	C++17	100 / 100	553 ms	87460 KiB

passport

#include <bits/stdc++.h>

using namespace std;

const int N = 800'000 + 10;
int n, q;
pair<int, int> range[N];

vector<pair<int, int>> ad[N];

vector<int> segments;
void collect(int s, int l, int r, int u, int v) { 
	if (v < l || u > r) return;
	if (u <= l && r <= v) {
		segments.push_back(s);
		return;
	}
	int mid = (l + r) >> 1;
	collect(s << 1, l, mid, u, v); 
	collect(s << 1 | 1, mid + 1, r, u, v);
}

int node[N], isLeaf[N];
void build(int s, int l, int r) { 
	if (l == r) { 
		node[l] = s;
		isLeaf[s] = true;
		return;
	}
	int mid = (l + r) >> 1;
	build(s << 1, l, mid); 
	build(s << 1 | 1, mid + 1, r);

	ad[s << 1].push_back({s, 0}); 
	ad[s << 1 | 1].push_back({s, 0});
}

const int MAX = 1'000'000;
void sktra(int* f, int st = -1) { 
	using pii = pair<int, int>;
	priority_queue<pii, vector<pii>, greater<>> q;
	if (st == -1) { 
		for (int i = 1; i <= 4 * n; ++i) q.push({f[i], i});
	} else { 
		fill(f + 1, f + 4 * n + 1, MAX);
		q.push({f[st] = 0, st});
	}
	while (q.size()) { 
		auto [d, u] = q.top(); q.pop();
		if (d != f[u]) continue;
		for (const auto& [v, w] : ad[u]) { 
			if (f[v] > d + w) q.push({f[v] = d + w, v});
		}
	}
}

int f[2][N], dis[N];

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;

	build(1, 1, n);
	for (int i = 1; i <= n; ++i) { 
		int l, r; cin >> l >> r;

		segments.clear();
		collect(1, 1, n, l, r);
		for (const auto& s : segments) ad[s].push_back({node[i], 1});
	}

	sktra(f[0], node[1]); 
	sktra(f[1], node[n]);
	
	for (int i = 1; i <= 4 * n; ++i) {
		dis[i] = f[0][i] + f[1][i];
		if (i != node[1] && i != node[n]) dis[i] -= isLeaf[i];
	}
	sktra(dis);

	cin >> q;
	while (q--) { 
		int x; cin >> x;
		cout << (dis[node[x]] > n ? -1 : dis[node[x]]) << "\n";
	}
}

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