← 返回题目列表

Codeforces · 1913/C

C. 多组游戏

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

在此问题中,您最初会得到一个空的多重集。您必须处理两种类型的查询:

1. ADD $$$x$$$ — 将等于 $$$2^{x}$$$ 的元素添加到多重集中;
2. GET $$$w$$$ — 说明是否可以对当前多重集的某个子集求和并得到等于 $$$w$$$ 的值。

输入

第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$) — 查询数量。

接下来是$$$m$$$行,每行包含两个整数$$$t_i$$$、$$$v_i$$$,表示第$$$i$$$个查询。如果 $$$t_i = 1$$$,则第 $$$i$$$ 查询为 ADD $$$v_i$$$ ($$$0 \le v_i \le 29$$$)。如果 $$$t_i = 2$$$,则第 $$$i$$$ 查询为 GET $$$v_i$$$ ($$$0 \le v_i \le 10^9$$$)。

输出

对于每个 GET 查询,如果可以选择总和等于 $$$w$$$ 的子集,则打印 YES,如果不可能,则打印 NO。

示例

输入 #1

5
1 0
1 0
1 0
2 3
2 4

输出 #1

YES
NO

输入 #2

7
1 0
1 1
1 2
1 10
2 4
2 6
2 7

输出 #2

YES
YES
YES