1913C.md (1122B)
1 Source: https://codeforces.com/problemset/problem/1913/C 2 3 C. Game with Multiset 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 In this problem, you are initially given an empty multiset. You have to process two types of queries: 22 23 1. ADD $x$ — add an element equal to $2^{x}$ to the multiset; 24 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$. 25 26 Input 27 28 The first line contains one integer $m$ ($1 \le m \le 10^5$) — the number of queries. 29 30 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$). 31 32 Output 33 34 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. 35 36 Examples 37 38 Input 39 40 ``` 41 5 42 43 1 0 44 45 1 0 46 47 1 0 48 49 2 3 50 51 2 4 52 ``` 53 54 Output 55 56 ``` 57 YES 58 NO 59 ``` 60 61 Input 62 63 ``` 64 7 65 66 1 0 67 68 1 1 69 70 1 2 71 72 1 10 73 74 2 4 75 76 2 6 77 78 2 7 79 ``` 80 81 Output 82 83 ``` 84 YES 85 YES 86 YES 87 ```