Submission #1089516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089516		ymm	Passport (JOI23_passport)	C++17	48 / 100	2099 ms	214796 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 {
	vector<set<pii>> vec;
	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 (l1 <= b && e <= r1) {
			auto it = vec[i].lower_bound(pii{l2, INT_MIN});
			if (it == vec[i].end() || it->second >= r2)
				return nullopt;
			return it->second;
		}
		if (r1 <= b || e <= l1)
			return nullopt;
		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) { return get(l1, r1, l2, r2, 0, 0, n); }

	void put(int p1, int p2, int x, int i, int b, int e) {
		vec[i].insert({p2, x});
		if (e-b == 1)
			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) {
		vec[i].erase({p2, x});
		if (e-b == 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);
	}
	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);
	}
	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);
	}
	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: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46