Submission #868733

#	Time	Username	Problem	Language	Result	Execution time	Memory
868733		NK_	Passport (JOI23_passport)	C++17	100 / 100	346 ms	48020 KiB

passport

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

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

	int N; cin >> N;

	int M = 1; while(M < N) M *= 2;

	V<vi> adj(2*M);
	auto add = [&](int l, int r, int i) {
		for(l += M, r += M+1; l < r; l /= 2, r /= 2) {
			if (l & 1) adj[l++].pb(i);
			if (r & 1) adj[--r].pb(i);
		}
	};

	for(int i = 0; i < N; i++) {
		int l, r; cin >> l >> r; --l, --r;
		add(l, r, i);
	}


	auto comp = [&](vi D) {
		vi vis(N), used(2*M);
		// cerr << "START" << endl;
		pq<pi> q;
		for(int i = 0; i < N; i++) if (D[i] != MOD) {
			q.push(mp(D[i], i));
		}

		while(sz(q)) {
			auto [d, x] = q.top(); q.pop();

			if (vis[x]) continue;
			vis[x] = 1;

			// cerr << x << " " << d << endl;

			int u = x + M;
			while(u > 0 && !used[u]) {
				used[u] = 1;
				for(auto& v : adj[u]) {
					if ((d + 1) < D[v]) {
						D[v] = d + 1;
						q.push(mp(D[v], v));
					}
				}
				u /= 2;
			}
		}

		// cerr << "END" << endl;
		return D;
	};

	vi L(N, MOD); L[0] = 0; L = comp(L);
	vi R(N, MOD); R[N-1] = 0; R = comp(R);


	vi ans(N); for(int i = 0; i < N; i++) {
		ans[i] = L[i] + R[i] - (i != 0 && i != N-1);
		// cerr << L[i] << " " << R[i] << " => " << ans[i] << endl;
	}
	ans = comp(ans);

	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int x; cin >> x; --x;
		cout << (ans[x] >= MOD ? -1 : ans[x]) << nl;
	}

	exit(0-0);
} 	 

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