oj.uz

Submission #963227

# Submission time Handle Problem Language Result Execution time Memory
963227 2024-04-14T18:59:34 Z dorulean Passport (JOI23_passport) C++17
100 / 100
 667 ms 86828 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define eb emplace_back

const int N = 2e5 + 5;
const int Inf = 0x3f3f3f3f;
int st[N], dr[N], n, q, x;
int dp[4 * N], dpl[4 * N], dpr[4 * N];
int sgt[4 * N];
vpii g[4 * N];

void build(int x, int l, int r) {
	if (l == r) {
		sgt[x] = l;
		return;
	}
	sgt[x] = x + n;
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	g[sgt[x << 1]].eb(sgt[x], 0);
	g[sgt[x << 1 | 1]].eb(sgt[x], 0);
}

void update(int x, int l, int r, int i) {
	if (st[i] <= l && r <= dr[i]) {
		g[sgt[x]].eb(i, 1);
		return;
	}
	int mid = (l + r) >> 1;
	if (st[i] <= mid)
		update(x << 1, l, mid, i);
	if (mid + 1 <= dr[i])
		update(x << 1 | 1, mid + 1, r, i);
}

void dijkstra(int* dp) {
	priority_queue<pii,vpii,greater<pii>> q;
	for (int i = 1; i <= n; ++i) {
		if (dp[i] < Inf) {
			q.emplace(dp[i], i);
		}
	}
	for (int i = n + 1; i <= 4 * n; ++i)
		dp[i] = Inf;
	while (!q.empty()) {
		int curr = q.top().first, u = q.top().second;
		q.pop();
		if (curr > dp[u]) continue;
		for (auto it : g[u])
			if (dp[it.first] > dp[u] + it.second) {
				dp[it.first] = dp[u] + it.second;
				q.emplace(dp[it.first], it.first);
			}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

 	cin >> n;
 	build(1, 1, n);
 
 	for (int i = 1; i <= n; ++i) {
 		cin >> st[i] >> dr[i];
 		dpl[i] = (st[i] == 1 ? 1 : Inf);
 		dpr[i] = (dr[i] == n ? 1 : Inf);
 		update(1, 1, n, i);
 	}
 	
 	dijkstra(dpl);
 	dijkstra(dpr);
 	
 	for (int i = 1; i <= n; ++i)
 		dp[i] = min(Inf, dpl[i] + dpr[i]);
 	
 	dijkstra(dp);
 	
 	for (cin >> q; q; --q) {
 		cin >> x;
 		cout << (dp[x] == Inf ? -1 : dp[x] - 1) << '\n';
 	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 667 ms 80712 KB Output is correct
5 Correct 266 ms 58376 KB Output is correct
6 Correct 149 ms 53040 KB Output is correct
7 Correct 173 ms 52252 KB Output is correct
8 Correct 108 ms 55752 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 7 ms 27228 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 6 ms 27272 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 6 ms 27328 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27228 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 7 ms 27228 KB Output is correct
16 Correct 9 ms 27736 KB Output is correct
17 Correct 9 ms 27480 KB Output is correct
18 Correct 8 ms 27736 KB Output is correct
19 Correct 8 ms 27736 KB Output is correct
20 Correct 7 ms 27632 KB Output is correct
21 Correct 8 ms 27520 KB Output is correct
22 Correct 8 ms 27484 KB Output is correct
23 Correct 8 ms 27484 KB Output is correct
24 Correct 7 ms 27740 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 7 ms 27228 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 6 ms 27272 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 6 ms 27328 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27228 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 7 ms 27228 KB Output is correct
16 Correct 9 ms 27736 KB Output is correct
17 Correct 9 ms 27480 KB Output is correct
18 Correct 8 ms 27736 KB Output is correct
19 Correct 8 ms 27736 KB Output is correct
20 Correct 7 ms 27632 KB Output is correct
21 Correct 8 ms 27520 KB Output is correct
22 Correct 8 ms 27484 KB Output is correct
23 Correct 8 ms 27484 KB Output is correct
24 Correct 7 ms 27740 KB Output is correct
25 Correct 6 ms 27308 KB Output is correct
26 Correct 6 ms 27228 KB Output is correct
27 Correct 10 ms 27776 KB Output is correct
28 Correct 9 ms 27484 KB Output is correct
29 Correct 8 ms 27484 KB Output is correct
30 Correct 8 ms 27484 KB Output is correct
31 Correct 9 ms 27484 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 667 ms 80712 KB Output is correct
5 Correct 266 ms 58376 KB Output is correct
6 Correct 149 ms 53040 KB Output is correct
7 Correct 173 ms 52252 KB Output is correct
8 Correct 108 ms 55752 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 6 ms 27228 KB Output is correct
11 Correct 7 ms 27228 KB Output is correct
12 Correct 5 ms 27224 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 6 ms 27272 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 6 ms 27328 KB Output is correct
19 Correct 6 ms 27228 KB Output is correct
20 Correct 6 ms 27228 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 6 ms 27228 KB Output is correct
23 Correct 7 ms 27228 KB Output is correct
24 Correct 9 ms 27736 KB Output is correct
25 Correct 9 ms 27480 KB Output is correct
26 Correct 8 ms 27736 KB Output is correct
27 Correct 8 ms 27736 KB Output is correct
28 Correct 7 ms 27632 KB Output is correct
29 Correct 8 ms 27520 KB Output is correct
30 Correct 8 ms 27484 KB Output is correct
31 Correct 8 ms 27484 KB Output is correct
32 Correct 7 ms 27740 KB Output is correct
33 Correct 6 ms 27308 KB Output is correct
34 Correct 6 ms 27228 KB Output is correct
35 Correct 10 ms 27776 KB Output is correct
36 Correct 9 ms 27484 KB Output is correct
37 Correct 8 ms 27484 KB Output is correct
38 Correct 8 ms 27484 KB Output is correct
39 Correct 9 ms 27484 KB Output is correct
40 Correct 638 ms 83056 KB Output is correct
41 Correct 304 ms 59456 KB Output is correct
42 Correct 385 ms 86364 KB Output is correct
43 Correct 373 ms 86828 KB Output is correct
44 Correct 173 ms 54200 KB Output is correct
45 Correct 195 ms 61488 KB Output is correct
46 Correct 119 ms 41232 KB Output is correct
47 Correct 360 ms 62380 KB Output is correct
48 Correct 293 ms 69300 KB Output is correct