Codeforces Round 905 (Div. 3) |
---|
Закончено |
Это простая версия задачи. Единственное различие состоит в том, что в этой версии $$$m = 1$$$.
Вам даны два массива целых чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$. До начала применения операций вы можете переупорядочить элементы каждого из массивов как угодно. Дальше за одну операцию вы делаете оба следующих действия, если массивы не пусты:
Пусть $$$k$$$ — итоговый размер обоих массивов. Вам нужно найти наименьшее количество операций, чтобы выполнялось $$$a_i < b_i$$$ для всех $$$1 \leq i \leq k$$$.
Эта задача была слишком проста и автор задачи решил ее усложнить. Вам также дано натуральное число $$$m$$$. Теперь вам нужно найти сумму ответов на задачу для $$$m$$$ пар массивов $$$(c[i], b)$$$, где $$$1 \leq i \leq m$$$. Массив $$$c[i]$$$ получается из $$$a$$$ следующим образом:
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$m = 1$$$) — размер массивов $$$a$$$ и $$$b$$$ и ограничения на значения элемента $$$a_1$$$.
Вторая строка каждого набора входных данных содержит $$$n - 1$$$ целое число $$$a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите суммарное количество наименьших операций по всем парам массивов $$$(c_i, b)$$$.
42 113 24 15 1 53 8 3 38 14 3 3 2 2 1 11 1 1 1 3 3 3 39 19 2 8 3 7 4 6 51 2 3 2 1 4 5 6 5
0 1 4 4
В первом наборе входных данных для пары массивов $$$([1, 1], [3, 2])$$$ ответ $$$0$$$. Можно не применять операции и не переставлять элементы.
Название |
---|