#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(2 * N), B(N), C(N);
for (auto& x : A) cin >> x;
for (auto& x : B) cin >> x;
for (auto& x : C) cin >> x;
sort(begin(B), end(B));
sort(begin(C), end(C));
vector<int> A2(A), B2(B), C2(C);
rotate(begin(A2), begin(A2) + N, end(A2));
reverse(begin(B2), end(B2));
reverse(begin(C2), end(C2));
for (auto& x : A2) x = -x;
for (auto& x : B2) x = -x;
for (auto& x : C2) x = -x;
auto check = [&](int thres) -> bool {
auto solve_sub = [&](const vector<int>& seedling, const vector<int>& planter) -> vector<bool> {
vector<int> imos(N + 1);
{
int p_l = 0, p_r = 0, s_r = 2 * N;
for (int i = 0; i < N; ++i) {
while (p_l < N && planter[p_l] < seedling[i] - thres) p_l += 1;
while (p_r < N && planter[p_r] <= seedling[i] + thres) p_r += 1;
while (s_r > N && seedling[s_r - 1] < seedling[i]) s_r -= 1;
int lowest = i - s_r + N;
if (p_r <= lowest) continue;
int l = max(0, i - p_r + 1);
int r = (p_l <= lowest ? i + 1 : i - p_l + 1);
if (l < r) {
imos[l] += 1;
imos[r] -= 1;
}
}
}
{
int p_l = N, p_r = N, s_r = N;
for (int i = N; i < 2 * N; ++i) {
while (p_l > 0 && planter[p_l - 1] >= seedling[i] - thres) p_l -= 1;
while (p_r > 0 && planter[p_r - 1] > seedling[i] + thres) p_r -= 1;
while (s_r > 0 && seedling[s_r - 1] > seedling[i]) s_r -= 1;
int lowest = s_r + N - i - 1;
if (p_r <= lowest) continue;
int l = (p_l <= lowest ? i - N + 1 : i + p_l - N + 1);
int r = min(N, i + p_r - N + 1);
if (l < r) {
imos[l] += 1;
imos[r] -= 1;
}
}
}
vector<bool> ret(N);
for (int i = 0; i < N; ++i) {
ret[i] = (imos[i] == N);
imos[i + 1] += imos[i];
}
return ret;
};
auto F1 = solve_sub(A, B);
auto F2 = solve_sub(A2, B2);
auto G1 = solve_sub(A, C);
auto G2 = solve_sub(A2, C2);
for (int i = 0; i < N; ++i) {
if (F1[i] && G2[i]) return true;
if (F2[i] && G1[i]) return true;
}
return false;
};
int ok = 1000000000, ng = -1;
while (ok - ng > 1) {
int md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
cout << ok << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
456 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
456 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
456 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
9 ms |
604 KB |
Output is correct |
27 |
Correct |
10 ms |
592 KB |
Output is correct |
28 |
Correct |
4 ms |
344 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
12 ms |
604 KB |
Output is correct |
31 |
Correct |
11 ms |
348 KB |
Output is correct |
32 |
Correct |
4 ms |
348 KB |
Output is correct |
33 |
Correct |
2 ms |
348 KB |
Output is correct |
34 |
Correct |
10 ms |
604 KB |
Output is correct |
35 |
Correct |
8 ms |
580 KB |
Output is correct |
36 |
Correct |
11 ms |
604 KB |
Output is correct |
37 |
Correct |
4 ms |
604 KB |
Output is correct |
38 |
Correct |
5 ms |
604 KB |
Output is correct |
39 |
Correct |
5 ms |
608 KB |
Output is correct |
40 |
Correct |
4 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1249 ms |
20108 KB |
Output is correct |
2 |
Correct |
1004 ms |
19240 KB |
Output is correct |
3 |
Correct |
827 ms |
16056 KB |
Output is correct |
4 |
Correct |
1200 ms |
20480 KB |
Output is correct |
5 |
Correct |
954 ms |
19240 KB |
Output is correct |
6 |
Correct |
30 ms |
860 KB |
Output is correct |
7 |
Correct |
562 ms |
23404 KB |
Output is correct |
8 |
Correct |
535 ms |
18128 KB |
Output is correct |
9 |
Correct |
1004 ms |
22756 KB |
Output is correct |
10 |
Correct |
1153 ms |
19464 KB |
Output is correct |
11 |
Correct |
1133 ms |
19720 KB |
Output is correct |
12 |
Correct |
1058 ms |
20472 KB |
Output is correct |
13 |
Correct |
923 ms |
18256 KB |
Output is correct |
14 |
Correct |
633 ms |
22764 KB |
Output is correct |
15 |
Correct |
569 ms |
19188 KB |
Output is correct |
16 |
Correct |
608 ms |
14892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
456 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
9 ms |
604 KB |
Output is correct |
27 |
Correct |
10 ms |
592 KB |
Output is correct |
28 |
Correct |
4 ms |
344 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
12 ms |
604 KB |
Output is correct |
31 |
Correct |
11 ms |
348 KB |
Output is correct |
32 |
Correct |
4 ms |
348 KB |
Output is correct |
33 |
Correct |
2 ms |
348 KB |
Output is correct |
34 |
Correct |
10 ms |
604 KB |
Output is correct |
35 |
Correct |
8 ms |
580 KB |
Output is correct |
36 |
Correct |
11 ms |
604 KB |
Output is correct |
37 |
Correct |
4 ms |
604 KB |
Output is correct |
38 |
Correct |
5 ms |
604 KB |
Output is correct |
39 |
Correct |
5 ms |
608 KB |
Output is correct |
40 |
Correct |
4 ms |
348 KB |
Output is correct |
41 |
Correct |
1249 ms |
20108 KB |
Output is correct |
42 |
Correct |
1004 ms |
19240 KB |
Output is correct |
43 |
Correct |
827 ms |
16056 KB |
Output is correct |
44 |
Correct |
1200 ms |
20480 KB |
Output is correct |
45 |
Correct |
954 ms |
19240 KB |
Output is correct |
46 |
Correct |
30 ms |
860 KB |
Output is correct |
47 |
Correct |
562 ms |
23404 KB |
Output is correct |
48 |
Correct |
535 ms |
18128 KB |
Output is correct |
49 |
Correct |
1004 ms |
22756 KB |
Output is correct |
50 |
Correct |
1153 ms |
19464 KB |
Output is correct |
51 |
Correct |
1133 ms |
19720 KB |
Output is correct |
52 |
Correct |
1058 ms |
20472 KB |
Output is correct |
53 |
Correct |
923 ms |
18256 KB |
Output is correct |
54 |
Correct |
633 ms |
22764 KB |
Output is correct |
55 |
Correct |
569 ms |
19188 KB |
Output is correct |
56 |
Correct |
608 ms |
14892 KB |
Output is correct |
57 |
Correct |
1380 ms |
22596 KB |
Output is correct |
58 |
Correct |
1553 ms |
16788 KB |
Output is correct |
59 |
Correct |
517 ms |
14228 KB |
Output is correct |
60 |
Correct |
1962 ms |
22888 KB |
Output is correct |
61 |
Correct |
1658 ms |
16588 KB |
Output is correct |
62 |
Correct |
604 ms |
15848 KB |
Output is correct |
63 |
Correct |
31 ms |
856 KB |
Output is correct |
64 |
Correct |
1274 ms |
23388 KB |
Output is correct |
65 |
Correct |
1258 ms |
17532 KB |
Output is correct |
66 |
Correct |
1872 ms |
20808 KB |
Output is correct |
67 |
Correct |
572 ms |
22768 KB |
Output is correct |
68 |
Correct |
731 ms |
21056 KB |
Output is correct |
69 |
Correct |
473 ms |
12896 KB |
Output is correct |
70 |
Correct |
706 ms |
22876 KB |
Output is correct |
71 |
Correct |
599 ms |
20444 KB |
Output is correct |
72 |
Correct |
697 ms |
22640 KB |
Output is correct |
73 |
Correct |
761 ms |
21088 KB |
Output is correct |
74 |
Correct |
1287 ms |
21948 KB |
Output is correct |
75 |
Correct |
835 ms |
12764 KB |
Output is correct |
76 |
Correct |
1269 ms |
22748 KB |
Output is correct |
77 |
Correct |
649 ms |
16552 KB |
Output is correct |