← 返回题目
题库练习 Game with Multiset
← 上一题 下一题 →

A16434 | Game with Multiset

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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$ .

输入格式

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$ ).

输出格式

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.

输入输出样例

输入 #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
C++ 编辑器
输入
输出