oj.uz

Submission #838206

# Submission time Handle Problem Language Result Execution time Memory
838206 2023-08-26T10:33:17 Z fatemetmhr Passport (JOI23_passport) C++17
48 / 100
 2000 ms 37408 KB 
// 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 lg    = 20;

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

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

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

	while(true){
		int v = -1;
		for(int i = 0; i < n; i++) if(!mark[i] && (v == -1 || ans[v] > ans[i]))
			v = i;
		if(v == -1)
			break;
		mark[v] = true;
		//debug(v);
		//debug(ans[v]);
		for(int i = 0; i < n; i++) 
			if(l[i] <= v && v <= r[i] && ans[i] > ans[v] + 1){
				assert(i);
				ans[i] = ans[v] + 1;
			}
		//debug(ans[4]);
	}

	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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Execution timed out 2060 ms 37408 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 24 ms 5412 KB Output is correct
17 Correct 18 ms 5456 KB Output is correct
18 Correct 20 ms 5436 KB Output is correct
19 Correct 19 ms 5428 KB Output is correct
20 Correct 18 ms 5588 KB Output is correct
21 Correct 20 ms 5636 KB Output is correct
22 Correct 21 ms 5460 KB Output is correct
23 Correct 18 ms 5464 KB Output is correct
24 Correct 21 ms 5432 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 24 ms 5412 KB Output is correct
17 Correct 18 ms 5456 KB Output is correct
18 Correct 20 ms 5436 KB Output is correct
19 Correct 19 ms 5428 KB Output is correct
20 Correct 18 ms 5588 KB Output is correct
21 Correct 20 ms 5636 KB Output is correct
22 Correct 21 ms 5460 KB Output is correct
23 Correct 18 ms 5464 KB Output is correct
24 Correct 21 ms 5432 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 2 ms 5076 KB Output is correct
27 Correct 26 ms 5428 KB Output is correct
28 Correct 19 ms 5460 KB Output is correct
29 Correct 20 ms 5588 KB Output is correct
30 Correct 20 ms 5512 KB Output is correct
31 Correct 19 ms 5452 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Execution timed out 2060 ms 37408 KB Time limit exceeded
5 Halted 0 ms 0 KB -