← 返回题目列表

Codeforces · 1547/E

E. 空调

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

在一块长度为 $$$n$$$ 的土地上,有 $$$k$$$ 空调:第 $$$i$$$ 空调放置在单元格 $$$a_i$$$ ($$$1 \le a_i \le n$$$) 中。两个或多个空调不能放置在同一单元中(即所有 $$$a_i$$$ 都是不同的)。

每台空调都有一个参数:温度。第 $$$i$$$ 空调设置为温度 $$$t_i$$$。

长度 $$$n=6$$$ 的条带示例,其中 $$$k=2$$$、$$$a=[2,5]$$$ 和 $$$t=[14,16]$$$。

对于每个单元格 $$$i$$$ ($$$1 \le i \le n$$$) 找到它的温度,可以通过公式 $$$$$$\min_{1 \le j \le k}(t_j + |a_j - i|),$$$$$$ 计算

其中 $$$|a_j - i|$$$ 表示 $$$a_j - i$$$ 之差的绝对值。

换句话说,单元$$$i$$$中的温度等于空调温度中的最小值,加上空调到单元$$$i$$$的距离。

让我们看一个例子。考虑$$$n=6,k=2$$$,第一台空调放置在单元格$$$a_1=2$$$中,并设置为温度$$$t_1=14$$$,第二台空调放置在单元格$$$a_2=5$$$中,并设置为温度$$$t_2=16$$$。在这种情况下,细胞内的温度为:

1. 单元$$$1$$$中的温度为:$$$\min(14 + |2 - 1|, 16 + |5 - 1|)=\min(14 + 1, 16 + 4)=\min(15, 20)=15$$$;
2. 单元$$$2$$$中的温度为:$$$\min(14 + |2 - 2|, 16 + |5 - 2|)=\min(14 + 0, 16 + 3)=\min(14, 19)=14$$$;
3. 单元$$$3$$$中的温度为:$$$\min(14 + |2 - 3|, 16 + |5 - 3|)=\min(14 + 1, 16 + 2)=\min(15, 18)=15$$$;
4. 单元$$$4$$$中的温度为:$$$\min(14 + |2 - 4|, 16 + |5 - 4|)=\min(14 + 2, 16 + 1)=\min(16, 17)=16$$$;
5. 单元$$$5$$$中的温度为:$$$\min(14 + |2 - 5|, 16 + |5 - 5|)=\min(14 + 3, 16 + 0)=\min(17, 16)=16$$$;
6. 单元$$$6$$$中的温度为:$$$\min(14 + |2 - 6|, 16 + |5 - 6|)=\min(14 + 4, 16 + 1)=\min(18, 17)=17$$$。

对于从 $$$1$$$ 到 $$$n$$$ 的每个单元格,找出其中的温度。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^4$$$) — 输入中测试用例的数量。然后是测试用例。每个测试用例之前都有一个空行。

每个测试用例包含三行。第一行包含两个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) 和 $$$k$$$ ($$$1 \le k \le n$$$) – 分别是土地的长度和空调的数量。

第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le n$$$) - 空调在土地上的位置。

第三行包含 $$$k$$$ 整数 $$$t_1, t_2, \ldots, t_k$$$ ($$$1 \le t_i \le 10^9$$$) — 空调温度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个由空格分隔的整数:电池中的空气温度。

示例

输入 #1

5

6 2
2 5
14 16

10 1
7
30

5 5
3 1 4 2 5
3 1 4 2 5

7 1
1
1000000000

6 3
6 1 3
5 5 5

输出 #1

15 14 15 16 16 17 
36 35 34 33 32 31 30 31 32 33 
1 2 3 4 5 
1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 
5 6 5 6 6 5