제출 #1158902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158902		vako_p	Passport (JOI23_passport)	C++20	40 / 100	1029 ms	207976 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];
pair<ll,ll> a[mxN],R[mxN][mxN],L[mxN][mxN];
bool vis[mxN];
vector<ll> vv,v[mxN];

struct segtree{
	vector<int> v;
	int sz;
	
	void init(){
		sz = 1;
		while(sz < n + 1) sz *= 2;
		v.assign(sz * 2, 1e9);
	}
	
	void set(int i, int val, int x, int l, int r){
		if(r - l == 1){
			v[x] = val;
			return;
		}
		int 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(int i, int val){
		set(i, val, 0, 0, sz);
	}
	
	int find(int l, int r, int x, int lx, int rx){
		if(lx >= l and rx <= r) return v[x];
		if(lx >= r or rx <= l) return 1e9;
		int mid = lx + (rx - lx) / 2;
		int m1 = find(l, r, x * 2 + 1, lx, mid);
		int m2 = find(l, r, x * 2 + 2, mid, rx);
		return min(m1, m2); 
	}
	
	int find(int l, int 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] = s.find(l, r) + 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;
	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: 0 / 8
• Subtask 5: 0 / 46