← 返回题目列表

Codeforces · 1075/B

B. 出租车司机和 Lyft

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

帕洛阿尔托是一座不寻常的城市,因为它是一条无尽的坐标线。它还因 Lyft 5 楼的办公室而闻名。

Lyft 变得如此受欢迎,以至于现在该市所有 $$$m$$$ 出租车司机都使用它,他们每天都会运送其他城市居民 — $$$n$$$ 乘客。

帕洛阿尔托的每个居民(包括出租车司机)都生活在其独特的位置(不存在坐标相同的一对居民)。

Lyft 系统非常聪明:当乘客呼叫出租车时,他的呼叫不会发送给所有出租车司机,而只会发送给距离该人最近的出租车司机。如果有多个距离相同的出租车司机,则选择坐标较小的出租车司机。

但有一天早上,出租车司机想知道:如果当天第一个叫出租车的乘客有多少人会打电话给给定的出租车司机?换句话说,您需要为每个出租车司机 $$$i$$$ 找到数字 $$$a_{i}$$$ - 当所有司机和乘客都在家时,会呼叫第 $$$i$$$ 出租车司机的乘客数量?

出租车司机既不能运送自己,也不能运送其他出租车司机。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 10^5$$$) — 乘客和出租车司机的数量。

第二行包含 $$$n + m$$$ 整数 $$$x_1, x_2, \ldots, x_{n+m}$$$ ($$$1 \le x_1 < x_2 < \ldots < x_{n+m} \le 10^9$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 个居民所在的坐标生活。

第三行包含 $$$n + m$$$ 整数 $$$t_1, t_2, \ldots, t_{n+m}$$$ ($$$0 \le t_i \le 1$$$)。如果 $$$t_i = 1$$$,则第 $$$i$$$ 位居民是出租车司机,否则 $$$t_i = 0$$$。

保证 $$$i$$$ 的数量使得 $$$t_i = 1$$$ 等于 $$$m$$$。

输出

打印 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_{m}$$$,其中 $$$a_i$$$ 是第 $$$i$$$ 出租车司机的答案。如果出租车司机住在所有出租车司机中第 $$$i$$$ 个最小坐标(请参阅示例以更好地理解),则该出租车司机的编号为 $$$i$$$。

示例

输入 #1

3 1
1 2 3 10
0 0 1 0

输出 #1

3

输入 #2

3 2
2 3 4 5 6
1 0 0 0 1

输出 #2

2 1

输入 #3

1 4
2 4 6 10 15
1 1 1 1 0

输出 #3

0 0 0 1

注意

在第一个示例中,我们只有一名出租车司机,这意味着任何 $$$n$$$ 乘客的订单都将发送给他。

在第二个示例中,第一个出租车司机住在坐标为 $$$2$$$ 的点,第二个出租车司机住在坐标为 $$$6$$$ 的点。显然,距居住在 $$$3$$$ 坐标上的乘客最近的出租车司机是第一个,距居住在 $$$5$$$ 坐标上的乘客最近的出租车司机是第二个。居住在 $$$4$$$ 坐标上的乘客与第一个和第二个出租车司机的距离相同,但由于第一个出租车司机的坐标较小,因此来自该乘客的呼叫将转至第一个出租车司机。

在第三个示例中,我们有一名乘客,离他最近的出租车司机是第四个。