Олимпиадный тренинг

Задача . C. Собеседование на работу


Задача

Темы: Бинарный поиск два указателя дп жадные алгоритмы реализация *1600

Монокарп открывает свою IT-компанию. Он хочет нанять \(n\) программистов и \(m\) тестировщиков.

На собеседование придут \(n+m+1\) кандидатов, пронумерованных от \(1\) до \(n+m+1\) в хронологическом порядке их прибытия. У \(i\)-го кандидата есть навык программирования \(a_i\) и навык тестирования \(b_i\) (навык программирования человека отличается от его навыка тестирования). Навык команды — это сумма навыков программирования всех нанятых в качестве программистов и сумма навыков тестирования всех нанятых в качестве тестировщиков.

Когда кандидат приходит на собеседование, Монокарп пытается назначить его на наиболее подходящую должность (если его навык программирования выше, то как программиста, в противном случае как тестировщика). Если все места для этой должности заняты, Монокарп назначает его на другую должность.

Ваша задача — для каждого кандидата рассчитать навык команды, если на собеседование придут все, кроме него. Обратите внимание, что это означает, что придут ровно \(n+m\) кандидатов, и все \(n+m\) мест в компании будут заняты.

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Каждый набор входных данных состоит из трех строк:

  • первая строка содержит два целых числа \(n\) и \(m\) (\(0 \le n, m \le 2 \cdot 10^5\); \(2 \le n + m + 1 \le 2 \cdot 10^5\)) — количество программистов и количество тестировщиков, которых Монокарп хочет нанять, соответственно;
  • вторая строка содержит \(n + m + 1\) целых чисел \(a_1, a_2, \dots, a_{n+m+1}\) (\(1 \le a_i \le 10^9\)), где \(a_i\) — навык программирования \(i\)-го кандидата;
  • третья строка содержит \(n + m + 1\) целых чисел \(b_1, b_2, \dots, b_{n+m+1}\) (\(1 \le b_i \le 10^9\); \(b_i \ne a_i\)), где \(b_i\) — навык тестирования \(i\)-го кандидата.

Дополнительное ограничение на входные данные: сумма \((n + m + 1)\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите \(n + m + 1\) целых чисел, где \(i\)-е число должно быть равно навыку команды, если на собеседование придут все, кроме \(i\)-го кандидата.

Примечание

Рассмотрим третий набор входных данных в примере:

  • если \(1\)-й кандидат не придет, \(2\)-го кандидата возьмут тестировщиком, \(3\)-го кандидата возьмут программистом, \(4\)-го кандидата возьмут тестировщиком. Суммарный навык команды будет \(2 + 5 + 1 = 8\);
  • если \(2\)-й кандидат не придет, \(1\)-го кандидата возьмут тестировщиком, \(3\)-го кандидата возьмут программистом, \(4\)-го кандидата возьмут тестировщиком. Суммарный навык команды будет \(5 + 5 + 1 = 11\);
  • если \(3\)-й кандидат не придет, \(1\)-го кандидата возьмут тестировщиком, \(2\)-го кандидата возьмут тестировщиком, \(4\)-го кандидата возьмут программистом. Суммарный навык команды будет \(5 + 2 + 4 = 11\);
  • если \(4\)-й кандидат не придет, \(1\)-го кандидата возьмут тестировщиком, \(2\)-го кандидата возьмут тестировщиком, \(3\)-го кандидата возьмут программистом. Суммарный навык команды будет \(5 + 2 + 5 = 12\).

Примеры
№Входные данныеВыходные данные
1 4
1 0
2 1
1 2
0 2
4 5 5
5 4 1
1 2
2 1 5 4
5 2 3 1
3 1
4 3 3 4 1
5 5 4 5 2 
1 2 
5 6 9 
8 11 11 12 
13 13 13 12 15

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет