310954: CF1913C. Game with Multiset

Memory Limit：256 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

C. Game with Multisettime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

In this problem, you are initially given an empty multiset. You have to process two types of queries:

  1. ADD $x$ — add an element equal to $2^{x}$ to the multiset;
  2. GET $w$ — say whether it is possible to take the sum of some subset of the current multiset and get a value equal to $w$.
Input

The first line contains one integer $m$ ($1 \le m \le 10^5$) — the number of queries.

Then $m$ lines follow, each of which contains two integers $t_i$, $v_i$, denoting the $i$-th query. If $t_i = 1$, then the $i$-th query is ADD $v_i$ ($0 \le v_i \le 29$). If $t_i = 2$, then the $i$-th query is GET $v_i$ ($0 \le v_i \le 10^9$).

Output

For each GET query, print YES if it is possible to choose a subset with sum equal to $w$, or NO if it is impossible.

ExamplesInput
5
1 0
1 0
1 0
2 3
2 4
Output
YES
NO
Input
7
1 0
1 1
1 2
1 10
2 4
2 6
2 7
Output
YES
YES
YES

Output

题目大意：本题中，你初始时有一个空的多集合。您必须处理两种类型的查询：

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. `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`。

Source/Category

加入题单

上一题 下一题 算法标签：