#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5;
const int MAX_VAL = 1e9;
int n;
int a[2 * MAX_N + 1], b[MAX_N + 1], c[MAX_N + 1];
int leftPos[2 * MAX_N + 1], rightPos[2 * MAX_N + 1];
int countLower[2 * MAX_N + 1];
int greaterSide[2 * MAX_N + 1];
int mars[2 * MAX_N + 1];
bool startB[2 * MAX_N + 1], startC[2 * MAX_N + 1];
bool checkMatch() {
bool isMatch = false;
for (int s = 1; s <= 2 * n; s++) {
int t = s + n;
if (t > 2 * n)
t -= 2 * n;
// printf("%d %d %d %d\n", s, t, startB[s], startC[t]);
isMatch |= (startB[s] & startC[t]);
}
// printf("%d\n", isMatch);
return isMatch;
}
void checkPositionsForColor(int d, int b[], bool start[]) {
// printf("\n\nFAC %d\n", d);
int j;
j = 0;
for (int i = 1; i <= n; i++) {
while (j + 1 <= n && b[j + 1] <= a[i] + d)
j++;
rightPos[i] = j;
}
j = 0;
for (int i = 2 * n; i >= n + 1; i--) {
while (j + 1 <= n && b[j + 1] <= a[i] + d)
j++;
rightPos[i] = j;
}
j = 1;
for (int i = 1; i <= n; i++) {
while (j <= n && b[j] < a[i] - d)
j++;
leftPos[i] = j;
}
j = 1;
for (int i = 2 * n; i >= n + 1; i--) {
while (j <= n && b[j] < a[i] - d)
j++;
leftPos[i] = j;
}
j = n + 1;
for (int i = n; i >= 1; i--) {
while (j + 1 <= 2 * n && a[j + 1] >= a[i])
j++;
countLower[i] = 2 * n - j;
greaterSide[i] = j;
}
j = n + 1;
for (int i = n + 1; i <= 2 * n; i++) {
while (j - 1 >= 1 && a[j - 1] > a[i])
j--;
countLower[i] = j - 1;
greaterSide[i] = j;
}
// for (int i = 1; i <= 2 * n; i++)
// printf("%d %d %d %d\n", leftPos[i], rightPos[i], countLower[i], greaterSide[i]);
// printf("\n");
//
for (int i = 0; i <= 2 * n; i++)
mars[i] = 0;
for (int i = 1; i <= n; i++) {
int l, r;
int t = greaterSide[i] - n;
if (i - t >= leftPos[i])
r = i;
else
r = min(i, i - leftPos[i] + 1);
if (i - t > rightPos[i])
l = n + 1;
else
l = max(1, i - rightPos[i] + 1);
if (l > r)
continue;
mars[l]++;
mars[r + 1]--;
}
for (int i = n + 1; i <= 2 * n; i++) {
int l, r;
int t = greaterSide[i];
if (n - i + t >= leftPos[i])
l = i + 1 - n;
else
l = max(i + 1 - n, leftPos[i] + i - n);
if (n - i + t > rightPos[i])
r = 0;
else
r = min(n, rightPos[i] + i - n);
// l = n + 1, r = 0;
// for (int s = i + 1 - n; s <= n; s++) {
// int p = n - i + max(s, greaterSide[i]);
// if (leftPos[i] <= p && p <= rightPos[i]) {
// l = min(l, s);
// r = max(r, s);
// }
// }
if (l > r)
continue;
mars[l]++;
mars[r + 1]--;
}
// printf("%d\n", d);
for (int i = n + 1; i <= 2 * n; i++) {
int l, r;
int t = n + 1 + countLower[i];
if (n - i + t < leftPos[i])
l = 2 * n + 1;
else
l = max(n + 1, leftPos[i] + i - n);
if (n - i + t <= rightPos[i])
r = i;
else
r = min(i, rightPos[i] + i - n);
// printf("DECI %d %d %d\n", i, l, r);
// int l = 2 * n + 1, r = 0;
// for (int s = n + 1; s <= i; s++) {
// int p = n - i + min(s, n + 1 + countLower[i]);
// if (leftPos[i] <= p && p <= rightPos[i]) {
// l = min(l, s);
// r = max(r, s);
// }
// }
if (l > r)
continue;
mars[l]++;
mars[r + 1]--;
}
// printf("\n");
for (int i = 1; i <= n; i++) {
int l = 2 * n + 1, r = 0;
for (int s = n + i + 1; s <= 2 * n; s++) {
int p = i + min(2 * n + 1 - s, countLower[i]);
// printf("%d %d->%d\n", i, s, p);
if (leftPos[i] <= p && p <= rightPos[i]) {
l = min(l, s);
r = max(r, s);
}
}
if (l > r)
continue;
mars[l]++;
mars[r + 1]--;
}
for (int i = 1; i <= 2 * n; i++) {
mars[i] += mars[i - 1];
start[i] = (mars[i] == n);
// printf("%d %d\n", mars[i], start[i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int maxval = 0;
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
cin >> a[i];
maxval = max(maxval, a[i]);
}
b[0] = -MAX_VAL;
for (int i = 1; i <= n; i++) {
cin >> b[i];
maxval = max(maxval, b[i]);
}
sort(b + 1, b + 1 + n);
c[0] = -MAX_VAL;
for (int i = 1; i <= n; i++) {
cin >> c[i];
maxval = max(maxval, c[i]);
}
sort(c + 1, c + 1 + n);
int l = -1, r = maxval;
// l = 1, r = 3;
while (r - l > 1) {
int d = (l + r) / 2;
checkPositionsForColor(d, b, startB);
checkPositionsForColor(d, c, startC);
if (checkMatch())
r = d;
else
l = d;
}
cout << r << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |