Submission #1089501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089501		ymm	Passport (JOI23_passport)	C++17	6 / 100	1929 ms	224744 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 Seg1 {
	vector<int> vec;
	int n;

	Seg1(int n) : vec(2*n, inf), n(n) {}

	void up(int i, int x) {
		i += n;
		while (0 < i) {
			vec[i] = min(vec[i], x);
			i /= 2;
		}
	}

	int get(int l, int r) {
		int ans = inf;
		l += n;
		r += n;
		while (l < r) {
			if (l&1) ans = min(ans, vec[l++]);
			if (r&1) ans = min(ans, vec[--r]);
			l /= 2;
			r /= 2;
		}
		return ans;
	}
};

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); }
};

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];
	}
	Seg1 sl(n), sr(n);
	sl.up(0, 0);
	sr.up(n-1, 0);
	Loop (i,1,n) {
		int x = sl.get(L[i], i+1) + 1;
		to_l[i] = x;
		sl.up(i, x);
	}
	LoopR (i,0,n-1) {
		int x = sr.get(i, R[i]+1) + 1;
		to_r[i] = x;
		sr.up(i, x);
	}
	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: 6 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46