← 返回题目列表

Codeforces · 1690/C

C. 恢复任务的持续时间

中文机器翻译题面 查看原题

最近,Polycarp 连续完成了 $$$n$$$ 任务。

对于每个已完成的任务,给出的时间 $$$s_i$$$ 是已知的,不会同时给出两个任务。还给出了任务完成的时间$$$f_i$$$。对于每个任务,都有一个未知值 $$$d_i$$$ ($$$d_i>0$$$) — 任务执行的持续时间。

已知任务是按其到来的顺序完成的。坡旅甲执行的任务如下:

- 第一个任务一到来,波利卡普就立即开始执行。
- 如果在 Polycarp 完成前一个任务之前到达了新任务,他会将新任务放在队列末尾。
- 当Polycarp执行完下一个任务并且队列不为空时,他立即从队列头部取出一个新任务(如果队列为空——他只是等待下一个任务)。

查找每个任务的$$$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$$$ — 每个任务的持续时间。

示例

输入 #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

输出 #1

2 7 1 
1 1 
1 183 1 60 7644 900 914 80152 5644467 
1000000000

注意

第一个测试用例:

队列一开始是空的:$$$[ ]$$$。这就是第一个任务的用武之地。在 $$$2$$$ 时刻,Polycarp 完成了第一个任务,因此第一个任务的持续时间为 $$$2$$$。队列是空的,所以波利卡普只是在等待。

在时间$$$3$$$,第二个任务到达。在 $$$7$$$ 时刻,第三个任务到达,现在队列如下所示:$$$[7]$$$。

在$$$10$$$时,Polycarp完成了第二个任务,因此第二个任务的持续时间为$$$7$$$。

在时间$$$10$$$,Polycarp 立即开始执行第三个任务并在时间$$$11$$$ 完成。因此,第三个任务的持续时间为 $$$1$$$。

第一个测试用例的示例。