Submission #1089534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089534		ymm	Passport (JOI23_passport)	C++17	100 / 100	527 ms	42692 KiB

passport

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 400'010;

int L[N], R[N];
int to_l[N], to_r[N];
int n, q;
int constexpr inf = 1e9;

struct Seg2 {
	struct Node {
		vector<pii> leaf;
		int mx = -1;
	};
	vector<Node> vec;
	bool made = 0;
	int n;

	Seg2(int n) : vec(4*n), n(n) {}

	optional<int> get(int l1, int r1, int l2, int r2, int i, int b, int e) {
		if (r1 <= b || e <= l1 || vec[i].mx < l2)
			return nullopt;
		if (e - b == 1)
			return vec[i].leaf.back().second;
		optional<int> ans = nullopt;
		if (!ans) ans = get(l1, r1, l2, r2, 2*i+1, b, (b+e)/2);
		if (!ans) ans = get(l1, r1, l2, r2, 2*i+2, (b+e)/2, e);
		return ans;
	}
	optional<int> get(int l1, int r1, int l2, int r2) { assert(r2 == n); assert(made); return get(l1, r1, l2, r2, 0, 0, n); }

	void make(int i, int b, int e) {
		if (e - b == 1) {
			sort(vec[i].leaf.begin(), vec[i].leaf.end());
			vec[i].mx = vec[i].leaf.size()? vec[i].leaf.back().first: -1;
			return;
		}
		make(2*i+1, b, (b+e)/2);
		make(2*i+2, (b+e)/2, e);
		vec[i].mx = max(vec[2*i+1].mx, vec[2*i+2].mx);
	}
	void make() { make(0, 0, n); made = 1; }

	void put(int p1, int p2, int x, int i, int b, int e) {
		if (e-b == 1) {
			vec[i].leaf.emplace_back(p2, x);
			return;
		}
		if (p1 < (b+e)/2)
			put(p1, p2, x, 2*i+1, b, (b+e)/2);
		else
			put(p1, p2, x, 2*i+2, (b+e)/2, e);
	}
	void put(int p1, int p2, int x) { put(p1, p2, x, 0, 0, n); }

	void remove(int p1, int p2, int x, int i, int b, int e) {
		if (e-b == 1) {
			assert(vec[i].leaf.size() && vec[i].leaf.back() == pii(p2, x));
			vec[i].leaf.pop_back();
			vec[i].mx = vec[i].leaf.size()? vec[i].leaf.back().first: -1;
			return;
		}
		if (p1 < (b+e)/2)
			remove(p1, p2, x, 2*i+1, b, (b+e)/2);
		else
			remove(p1, p2, x, 2*i+2, (b+e)/2, e);
		vec[i].mx = max(vec[2*i+1].mx, vec[2*i+2].mx);
	}
	void remove(int p1, int p2, int x) { remove(p1, p2, x, 0, 0, n); }
};

void single_bfs(int s, int dis[])
{
	fill(dis, dis+n, inf);
	dis[s] = 0;
	vector<int> vec = {s};
	Seg2 seg(n);
	Loop (i,0,n) {
		if (i != s)
			seg.put(L[i], R[i], i);
	}
	seg.make();
	Loop (i,0,vec.size()) {
		int v = vec[i];
		optional<int> ou;
		while ((ou = seg.get(0, v+1, v, n))) {
			int u = *ou;
			dis[u] = dis[v] + 1;
			vec.push_back(u);
			seg.remove(L[u], R[u], u);
		}
	}
}

int dis[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		cin >> L[i] >> R[i];
		--L[i]; --R[i];
	}
	single_bfs(0, to_l);
	single_bfs(n-1, to_r);
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	Seg2 seg(n);
	Loop (i,0,n) {
		dis[i] = to_l[i] + to_r[i] - (i != 0 && i != n-1);
		pq.emplace(dis[i], i);
		seg.put(L[i], R[i], i);
	}
	seg.make();
	while (pq.size()) {
		auto [d, i] = pq.top();
		pq.pop();
		if (d != dis[i])
			continue;
		optional<int> oj;
		while ((oj = seg.get(0, i+1, i, n))) {
			int j = *oj;
			seg.remove(L[j], R[j], j);
			if (dis[j] <= d + 1)
				continue;
			//cerr << i << " updates " << j << " to " << d + 1 << '\n';
			dis[j] = d + 1;
			pq.emplace(dis[j], j);
		}
	}
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		cout << (dis[x-1] >= inf? -1: dis[x-1]) << '\n';
	}
}

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