Задача №114593. Только длинные галстуки
Вы когда-нибудь слышали о компании Bubble Kvas Aesc? Эта компания известна своими «только странными изобретениями». Для краткости мы будем называть эту компанию как BKA.
BKA изобрела новый продукт под названием «Только Длинные Галстуки». Всего существует \(N + 1\) галстуков, пронумерованных от 1 до \(N + 1\). Длина \(i\)-го галстука равна \(A_i\).
Компания собрала своих сотрудников на вечеринку. Всего на вечеринку приглашены \(N\) сотрудников, куда \(j\)-й сотрудник наденет галстук длиной \(B_j\).
Вечеринка пройдёт по следующей схеме:
- Глава компании BKA выбирает галстук, который затем не будет использован на вечеринке.
- Каждый из сотрудников выбирает один из оставшихся галстуков. При этом никакие два сотрудника не могут надеть один и тот же галстук.
- Каждый сотрудник снимает галстук, в котором он изначально пришёл, и надевает тот, который был выбрал на предыдущем шаге.
Если изначально сотрудник пришёл с галстуком длиной \(b\) и пытается надеть галстук длины \(a\), то его чувство непривычности равно \(max(a - b, 0)\). Значение чудоковатости вечеринки равно максимуму из всех непривычностей сотрудников.
Также мы определим \(C_k\) как минимально возможное значение чудоковатости вечеринки при условии, что глава компании выбрал галстук под номером \(k\).
Требуется написать программу, которая вычисляет значения \(C_1, C_2, \dots, C_{N+1}\).
Первая строка содержит натуральное число \(N\) \((1 \le N \le 2 \cdot 10^5)\).
Вторая строка содержит натуральные числа \(A_1 \dots A_{N+1}\) \((1 \le A_i \le 10^9)\).
Третья строка содержит натуральные числа \(B1 \dots B_N\) \((1 \le B_j \le 10^9)\).
Выведите значения \(C_1, C_2, \dots , C_{N+1}\).
| Подзадача 1 (13 балл) | \(N \le 10\). |
| Подзадача 2 (26 баллов) | \(N \le 2000\). |
| Подзадача 3 (61 балл) | \(N \le 2 \cdot 10^5\). |
Рассмотрим первый пример.
- Глава компании BKA выбирает 4-й галстук, который затем не будет использован на вечеринке.
- Первый сотрудник выбирает 1-й галстук, второй сотрудник выбирает 2-й галстук, третий сотрудник выбирает 3-й галстук.
- Каждый сотрудник надевает выбранный им галстук.
В этом случае, значения непривычностей каждого сотрудника равны 2, 0, 3 соответственно. Следовательно, значение чудоковатости вечеринки равно 3.
Однако возможно уменьшить значение чудоковатости вечеринки до 1, если сотрудники выберут другие галстуки.
- Глава компании BKA выбирает 4-й галстук, который затем не будет использован на вечеринке.
- Первый сотрудник выбирает 2-й галстук, второй сотрудник выбирает 3-й галстук, третий сотрудник выбирает 1-й галстук.
- Каждый сотрудник надевает выбранный им галстук.
В этом случае, значения непривычностей каждого сотрудника равны 1, 1, 0 соответственно. Следовательно, значение чудоковатости вечеринки равно 1.
Это значение чудоковатости является минимальным из всех возможных при условии, что глава компании выбрал 4-й галстук. Следовательно, \(C_4 = 1\).
3 4 3 7 6 2 6 4
2 2 1 1
5 4 7 9 10 11 12 3 5 7 9 11
4 4 3 2 2 2