Game with Multiset
Contest: Educational Codeforces Round 160 (Rated for Div. 2)
Difficulty rating: 1300
Tags: binary search, bitmasks, brute force, greedy

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 format:
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 format:
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.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Example input:
5
1 0
1 0
1 0
2 3
2 4

Example output:
YES
NO

Example input:
7
1 0
1 1
1 2
1 10
2 4
2 6
2 7

Example output:
YES
YES
YES

Editorial:
We are given a classic knapsack problem. There are items with certain weights and a total weight that we want to achieve. If the weights were arbitrary, we would need dynamic programming to solve it. However, this variation of the knapsack problem can be solved greedily. What makes it special? If we arrange the weights in non-decreasing order, each subsequent weight is divisible by the previous one.
Then the following greedy approach works. Arrange the items by weight, from smallest to largest. Let's say we want to achieve sum $$$s$$$, and the weights of the items are $$$x_1, x_2, \dots$$$. Let the weights be distinct, and the number of items with weight $$$x_i$$$ be $$$\mathit{cnt}_i$$$.
If $$$s$$$ is not divisible by $$$x_1$$$, the answer is NO. Otherwise, we look at the remainder of $$$s$$$ divided by $$$x_2$$$. If it is not equal to $$$0$$$, our only hope to make it $$$0$$$ is to take items with weight $$$x_1$$$. All other items are divisible by $$$x_2$$$, so they will not help. We take exactly $$$\frac{s \bmod x_2}{x_1}$$$ items. If there are less than that, the answer is NO.
Subtract this from $$$s$$$ — now the remainder is $$$0$$$. Now the claim is: there is no point in taking additional items with weight $$$x_1$$$ in a quantity not divisible by $$$\frac{x_2}{x_1}$$$. If we do that, we will break the remainder again. Thus, we can pack $$$\frac{x_2}{x_1}$$$ items with weight $$$x_1$$$ into groups of weight $$$x_2$$$ and add the number of these groups to $$$\mathit{cnt}_2$$$. Then recursively solve the same problem, but for the new value of $$$s$$$ and weights $$$2, 3, \dots$$$.
When we run out of distinct weights, we have to check that there are enough items of the largest weight to collect the entire weight $$$s$$$.
This can be written by iterating through the weight values from smallest to largest. For each weight, we can maintain the count in an array. Then the first type of query works in $$$O(1)$$$, and the second type of query works in $$$30$$$ iterations.