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

Задача . C. Восстановление длительности выполнения заданий

Задача

Темы: жадные алгоритмы реализация Структуры данных *800

Недавно Поликарп выполнил $n$ последовательно пришедших заданий.

Для каждого выполненного задания известно время $s_i$, когда оно было дано, никакие два задания не были даны в одно и то же время. Также дано время $f_i$, когда задание было выполнено. Для каждого задания есть неизвестная величина $d_i$ ($d_i>0$) — длительность выполнения задания.

Известно, что задания были выполнены в том порядке, в котором пришли. Поликарп выполнял задания следующим образом:

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

Найдите $d_i$ (длительность выполнения) каждого задания.

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

В первой строке записано единственное число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $n$ ($1 \le n \le 2 \cdot 10^5$).

Во второй строке каждого набора входных данных записано ровно $n$ целых чисел $s_1 < s_2 < \dots < s_n$ ($0 \le s_i \le 10^9$).

В третьей строке каждого набора входных данных записано ровно $n$ целых чисел $f_1 < f_2 < \dots < f_n$ ($s_i < f_i \le 10^9$).

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $2 \cdot 10^5$.

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

Для каждого из $t$ наборов входных данных выведите $n$ положительных целых чисел $d_1, d_2, \dots, d_n$ — длительности выполнения каждого задания.

Примечание

Первый набор входных данных:

В начале очередь пуста: $[ ]$. И туда сразу приходит первое задание. В момент времени $2$ Поликарп заканчивает делать первое задание, соответственно, длительность выполнения первого задания — $2$. Очередь пуста, поэтому Поликарп просто ждёт.

В момент времени $3$ приходит второе задание. А в момент времени $7$ приходит третье задание, и теперь очередь выглядит так: $[7]$.

В момент времени $10$ Поликарп заканчивает делать второе задание, в итоге длительность выполнения второго задания — $7$.

И в момент времени $10$ Поликарп сразу начинает делать третье задание и заканчивает в момент времени $11$. В итоге длительность выполнения третьего задания — $1$.

$\text{[math]}$ Пример первого набора входных данных.

Примеры

№	Входные данные	Выходные данные
1	4 3 0 3 7 2 10 11 2 10 15 11 16 9 12 16 90 195 1456 1569 3001 5237 19275 13 199 200 260 9100 10000 10914 91066 5735533 1 0 1000000000	2 7 1 1 1 1 183 1 60 7644 900 914 80152 5644467 1000000000

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

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

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

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

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

Нет