Submission #1304650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304650		vlomaczk	Passport (JOI23_passport)	C++20	0 / 100	659 ms	1114112 KiB

passport

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll base = 1<<18;
ll inf = 1e18;

struct TreeMax {
	vector<pair<ll, ll>> Tree;

	TreeMax() : Tree(2*base, {-inf, -inf}) {}

	void upd(ll x, pair<ll,ll> val) {
		x+=base;
		Tree[x] = {val.second, -val.first};
		x/=2;
		while(x>0) {
			Tree[x] = max(Tree[x+x], Tree[x+x+1]);
			x/=2;
		}
	}

	pair<ll, ll> query(ll a, ll b) {
		if(a==b) return {-Tree[a+base].second, Tree[a+base].first};
		a+=base-1;
		b+=base+1;
		pair<ll,ll> ans = {-inf,-inf};
		while(a/2 != b/2) {
			if(a%2==0) ans = max(ans, Tree[a+1]);
			if(b%2==1) ans = max(ans, Tree[b-1]);
			a/=2; b/=2;
		}
		return {-ans.second, ans.first};
	}
};

struct TreeMin {
	vector<pair<ll, ll>> Tree;

	TreeMin() : Tree(2*base, {inf, inf}) {}

	void upd(ll x, pair<ll,ll> val) {
		x+=base;
		Tree[x] = {val.first, -val.second};
		x/=2;
		while(x>0) {
			Tree[x] = min(Tree[x+x], Tree[x+x+1]);
			x/=2;
		}
	}

	pair<ll, ll> query(ll a, ll b) {
		if(a==b) return {Tree[a+base].first, -Tree[a+base].second};
		a+=base-1;
		b+=base+1;
		pair<ll,ll> ans = {inf,inf};
		while(a/2 != b/2) {
			if(a%2==0) ans = min(ans, Tree[a+1]);
			if(b%2==1) ans = min(ans, Tree[b-1]);
			a/=2; b/=2;
		}
		return {ans.first, -ans.second};
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n;
	cin >> n;
	vector<ll> l(n), r(n);
	for(ll i=0; i<n; ++i) cin >> l[i] >> r[i];
	TreeMin left;
	TreeMax right;
	for(ll i=0; i<n; ++i) {
		l[i]--; r[i]--;
		left.upd(i, {l[i], r[i]});
		right.upd(i, {l[i], r[i]});
	}
	vector<vector<vector<pair<ll, ll>>>> g(n+1, vector<vector<pair<ll, ll>>>(n+1));
	for(ll i=0; i<n; ++i) {
		for(ll j=i; j<n; ++j) {
			pair<ll, ll> L = left.query(i,j);
			L.first = min(L.first, i);
			L.second = max(L.second, j);

			pair<ll, ll> R = right.query(i,j);
			R.first = min(R.first, i);
			R.second = max(R.second, j);

			g[L.first][L.second].push_back({i,j});
			g[R.first][R.second].push_back({i,j});

			// cout << "(" << i << " " << j << ") -> (" << L.first << " " << L.second << ")\n";
			// cout << "(" << i << " " << j << ") -> (" << R.first << " " << R.second << ")\n";
		}
	}
	vector<vector<ll>> dist(n+1, vector<ll>(n+1, inf));
	dist[0][n-1] = 0;
	queue<pair<ll, ll>> Q;
	Q.push({0,n-1});
	while(Q.size()) {
		auto[a,b] = Q.front(); Q.pop();
		for(auto[c,d] : g[a][b]) {
			if(dist[c][d]==inf) {
				dist[c][d] = dist[a][b] + 1;
				Q.push({c,d});
			}
		}
	}
	ll q; cin >> q;
	while(q--) {
		ll x; cin >> x; --x;
		if(dist[x][x] == inf) cout << "-1\n";
		else cout << dist[x][x] << "\n";
	}

	return 0;
}

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