Submission #838219

#	Time	Username	Problem	Language	Result	Execution time	Memory
838219		fatemetmhr	Passport (JOI23_passport)	C++17	100 / 100	272 ms	71716 KiB

passport

// na hanooz omidi vjood dare... hanooz ye karayi hast ke bknm :)

#include <bits/stdc++.h>

using namespace std;


#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   (x).begin(), (x).end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;
const int lg    = 20;

int suf[maxn5], pre[maxn5], ans[maxn5];
int l[maxn5], r[maxn5];
bool mark[maxn5], done[maxn5];
int dp[maxn5];
vector <int> adj[maxn5], rt, av[maxn5];

namespace rmq{

	pair <int, int> mn[lg][maxn5];

	void build(int n){
		for(int i = 1; i < lg; i++) for(int j = 0; j + (1 << i) - 1 < n; j++)
			mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
	}

	pair <int, int> get_min(int l, int r){
		int k = 31 - __builtin_clz(r - l + 1);
		return min(mn[k][l], mn[k][r - (1 << k) + 1]);
	}
}

namespace seg{
	
	pair <int, int> mn[maxnt], mx[maxnt];

	void build(int l, int r, int v){
		if(r - l == 1){
			mn[v] = {::l[l], l};
			mx[v] = {::r[l], l};
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, v * 2);
		build(mid, r, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}

	void rem(int l, int r, int id, int v){
		if(r - l == 1){
			mn[v] = {maxn5, l};
			mx[v] = {-1, l};
			return;
		}
		int mid = (l + r) >> 1;
		if(id < mid)
			rem(l, mid, id, v * 2);
		else
			rem(mid, r, id, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}

	pair <int, int> get_max(int l, int r, int lq, int rq, int v){
		if(rq <= l || r <= lq)
			return mp(-1, -1);
		if(lq <= l && r <= rq)
			return mx[v];
		int mid = (l + r) >> 1;
		return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
	}

	pair <int, int> get_min(int l, int r, int lq, int rq, int v){
		if(rq <= l || r <= lq)
			return mp(maxn5, -1);
		if(lq <= l && r <= rq)
			return mn[v];
		int mid = (l + r) >> 1;
		return min(get_min(l, mid, lq, rq, v * 2), get_min(mid, r, lq, rq, v * 2 + 1));
	}
}

void dfs(int v){
	for(auto u : adj[v]){
		dp[u] = min(dp[u], dp[v] + 1);
		dfs(u);
	}
}



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

	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> l[i] >> r[i];
		l[i]--; r[i]--;
		rmq::mn[0][i] = {l[i], i};
	}
	rmq::build(n);
	fill(dp, dp + n + 5, maxn5);
	for(int i = 0; i < n; i++){
		int v = rmq::get_min(l[i], r[i]).se;
		if(l[i] == 0)
			dp[i] = 0;
		if(i != v)
			adj[v].pb(i);
		else
			rt.pb(i);
	}
	for(auto u : rt)
		dfs(u);
	for(int i = 0; i < n; i++){
		pre[i] = dp[i];
		adj[i].clear();
	}
	rt.clear();


	for(int i = 0; i < n; i++)
		rmq::mn[0][i] = {-r[i], i};
	rmq::build(n);

	fill(dp, dp + n + 5, maxn5);
	for(int i = 0; i < n; i++){
		int v = rmq::get_min(l[i], r[i]).se;
		if(r[i] == n - 1)
			dp[i] = 0;
		if(i != v)
			adj[v].pb(i);
		else
			rt.pb(i);
	}
	for(auto u : rt)
		dfs(u);
	for(int i = 0; i < n; i++){
		suf[i] = dp[i];
		adj[i].clear();
		ans[i] = min(maxn5, pre[i] + suf[i]);
		if(ans[i] < maxn5)
			av[ans[i]].pb(i);
	}


	seg::build(0, n, 1);

	for(int i = 0; i < maxn5; i++) for(int j = 0; j < int(av[i].size()); j++){
		int v = av[i][j];
		if(done[v])
			continue;
		done[v] = mark[v] = true;
		//debug(v);
		//debug(ans[v]);
		pair <int, int> best;
		while((best = seg::get_max(0, n, 0, v, 1)).fi >= v){
			int u = best.se;
			//debug(u);
			if(!mark[u]){
				mark[u] = true;
				ans[u] = min(ans[u], ans[v] + 1);
				av[ans[u]].pb(u);
			}
			seg::rem(0, n, u, 1);
		}
		while((best = seg::get_min(0, n, v + 1, n, 1)).fi <= v){
			int u = best.se;
			//debug(u);
			if(!mark[u]){
				mark[u] = true;
				ans[u] = min(ans[u], ans[v] + 1);
				av[ans[u]].pb(u);
			}
			seg::rem(0, n, u, 1);
		}
	}

	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int x; cin >> x;
		x--;
		cout << (ans[x] >= maxn5 ? -1 : ans[x] + 1) << '\n';
	}

}

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