← 返回题目列表

Codeforces · 1170/E

E. 推拉门

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

想象一下,您是一家大型老式公司的首席执行官。与任何现代和进步的公司(例如 JetBrains)不同,您的公司有着装要求。这就是为什么您已经为您的员工分配了一个宽敞的房间,让他们可以更衣。此外,您已经购买了$$$m$$$隔间衣柜,因此第$$$i$$$个员工可以将他/她的物品存放在第$$$i$$$个单元格中(当然,所有隔间的宽度都相同)。

出现问题:衣柜有推拉门!更具体地说,衣柜有 $$$n$$$ 个门(从左到右编号),第 $$$j$$$ 个门的宽度等于 $$$a_j$$$ 衣柜单元格的宽度。衣柜有单轨,因此没有两扇门可以滑过。

衣柜的极其示意性示例:$$$m=9$$$、$$$n=2$$$、$$$a_1=2$$$、$$$a_2=3$$$。

问题如下:有时要打开某些单元格,您必须关闭其他一些单元格(因为所有门都放置在单个轨道上)。例如,如果您有一个 $$$4$$$ 隔间衣柜(即 $$$m=4$$$),带有 $$$n=2$$$ 单格门(即 $$$a_1=a_2=1$$$),并且您需要打开 $$$1$$$-st 和 $$$3$$$-rd 单元,则必须关闭 $$$2$$$-nd 和 $$$1$$$-rd 单元。 $$$4$$$ 个单元格。

作为首席执行官,您对接下来的 $$$q$$$ 天有完整的日程安排。现在您想知道:第 $$$k$$$ 天来的所有员工是否可以同时访问他们的牢房?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 4 \cdot 10^5$$$) — 分别是门和隔间的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$, $$$\sum{a_i} \le m$$$) — 相应的门宽度。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 您必须处理的天数。

接下来的 $$$q$$$ 行描述了每天的日程安排。每个计划都表示为一个整数 $$$c_k$$$ 后跟 $$$c_k$$$ 整数 $$$w_1, w_2, \dots, w_{c_k}$$$ ($$$1 \le c_k \le 2 \cdot 10^5$$$, $$$1 \le w_1 < w_2 < \dots < w_{c_k} \le m$$$) — 员工数量谁将在第 $$$k$$$ 天到来,以及他们的指数按升序排列。

保证 $$$\sum{c_k}$$$ 不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$q$$$ 答案。每个答案都是“是”或“否”(不区分大小写)。如果可能,当天的所有员工都可以同时进入他们的隔间,请打印“是”。

示例

输入 #1

3 10
2 3 2
6
1 5
2 1 10
2 2 9
2 5 6
3 1 7 8
4 1 2 3 4

输出 #1

YES
YES
NO
NO
YES
NO