Submission #1158912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158912		vako_p	Passport (JOI23_passport)	C++20	48 / 100	993 ms	208032 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define debug(x) cerr << '\n' << __LINE__ << ": " << (#x) << " is " << (x) << endl;
//#define cerr if(false) cerr

const int mxN = 3005;
ll n,dp[mxN][mxN],ans[mxN],R1[1000005];
pair<ll,ll> a[mxN],R[mxN][mxN],L[mxN][mxN];
bool vis[mxN];
vector<ll> vv,v[mxN];

struct segtree{
	vector<ll> v;
	ll sz;
	
	void init(){
		sz = 1;
		while(sz < n + 1) sz *= 2;
		v.assign(sz * 2, 1e9);
	}
	
	void set(ll i, ll val, ll x, ll l, ll r){
		if(r - l == 1){
			v[x] = val;
			return;
		}
		ll mid = l + (r - l) / 2;
		if(mid > i) set(i, val, x * 2 + 1, l, mid);
		else set(i, val, x * 2 + 2, mid, r);
		v[x] = min(v[x * 2 + 1], v[x * 2 + 2]);
		
	}
	
	void set(ll i, ll val){
		set(i, val, 0, 0, sz);
	}
	
	int find(ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= l and rx <= r) return v[x];
		if(lx >= r or rx <= l) return 1e9;
		ll mid = lx + (rx - lx) / 2;
		return min(find(l, r, x * 2 + 1, lx, mid), find(l, r, x * 2 + 2, mid, rx)); 
	}
	
	int find(ll l, ll r){
		return find(l, r, 0, 0, sz);
	}
};

segtree s;

ll dfs(ll at, ll val){
	if(val >= a[at].first and val <= a[at].second) val = a[at].first;
	if(dp[at][val] < 1e9) return dp[at][val];
	ll l = min(val, a[at].first), r = max(a[at].second, val);
	if(l == 1 and r == n){
		dp[at][val] = 0;
		return 0;
	}
	dp[at][val] = min((int)1e9, s.find(l, r + 1) + 1);
	if(R[l][r].first > r) dp[at][val] = min(dp[at][val], 1LL + dfs(R[l][r].second, l));
	if(L[l][r].first < l) dp[at][val] = min(dp[at][val], 1LL + dfs(L[l][r].second, r));
	return dp[at][val];
}

void dfs1(ll at){
	if(vis[at]) return;
	vis[at] = true;
	for(auto it : v[at]) dfs1(it);
	vv.pb(at);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	if(n >= mxN){
		for(int i = 1; i <= n; i++){
			cin >> a[i].first >> a[i].second;
			R1[i] = max(R1[i - 1], a[i].second);
		}
		ll q;
		cin >> q;
		while(q--){
			ll x;
			cin >> x;
			ll res = 1;
			while(x < n){
				if(R1[x] <= x){
					res = -1;
					break;
				}
				x = R1[x];
				res++;
			}
			cout << res << '\n';
		}
		return 0;
	}
	s.init();
	for(int i = 1; i <= n; i++){
		cin >> a[i].first >> a[i].second;
		for(int j = 1; j < i; j++){
			if(a[i].first < a[j].first and a[i].second > a[j].second)
				v[i].pb(j);
			if(a[j].first < a[i].first and a[j].second > a[i].second)
				v[j].pb(i);
		}
		for(int j = 0; j <= n; j++) dp[i][j] = 1e9;
	}	
	for(int i = 1; i <= n; i++){
		L[i][i - 1].first = 1e9;
		for(int j = i; j <= n; j++){
			R[i][j] = max(R[i][j - 1], make_pair(a[j].second, (ll)j));
			L[i][j] = min(L[i][j - 1], make_pair(a[j].first, (ll)j));
		}
	}
	for(int i = 1; i <= n; i++)
		dfs1(i);
	for(int i = n - 1; i >= 0; i--){
		ans[vv[i]] = dfs(vv[i], a[vv[i]].first); 
		s.set(vv[i], ans[vv[i]]);
	}
	ll q;
	cin >> q;
	while(q--){
		ll x;
		cin >> x;
		if(ans[x] >= n) cout << -1 << '\n';
		else cout << ans[x] + 1 << '\n';
	}
}

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