Codeforces Round 905 (Div. 3) |
---|
Закончено |
Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$m \leq 10^9$$$.
Вам даны два массива целых чисел $$$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$$$, $$$1 \leq m \leq 10^9$$$) — размер массивов $$$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 413 24 75 1 53 8 3 38 44 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
2 12 16 4
В первом наборе входных данных:
Название |
---|