1732D1.md (2401B)
1 Source: https://codeforces.com/problemset/problem/1732/D1 2 3 D1. Balance (Easy version) 4 5 time limit per test 6 7 3 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 This is the easy version of the problem. The only difference is that in this version there are no "remove" queries. 22 23 Initially you have a set containing one element — $0$. You need to handle $q$ queries of the following types: 24 25 * + $x$ — add the integer $x$ to the set. It is guaranteed that this integer is not contained in the set; 26 * ? $k$ — find the $k\text{-mex}$ of the set. 27 28 In our problem, we define the $k\text{-mex}$ of a set of integers as the smallest non-negative integer $x$ that is divisible by $k$ and which is not contained in the set. 29 30 Input 31 32 The first line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries. 33 34 The following $q$ lines describe the queries. 35 36 An addition query of integer $x$ is given in the format + $x$ ($1 \leq x \leq 10^{18}$). It is guaranteed that $x$ was not contained in the set. 37 38 A search query of $k\text{-mex}$ is given in the format ? $k$ ($1 \leq k \leq 10^{18}$). 39 40 It is guaranteed that there will be at least one query of type ?. 41 42 Output 43 44 For each query of type ? output a single integer — the $k\text{-mex}$ of the set. 45 46 Examples 47 48 Input 49 50 ``` 51 15 52 53 + 1 54 55 + 2 56 57 ? 1 58 59 + 4 60 61 ? 2 62 63 + 6 64 65 ? 3 66 67 + 7 68 69 + 8 70 71 ? 1 72 73 ? 2 74 75 + 5 76 77 ? 1 78 79 + 1000000000000000000 80 81 ? 1000000000000000000 82 ``` 83 84 Output 85 86 ``` 87 3 88 6 89 3 90 3 91 10 92 3 93 2000000000000000000 94 ``` 95 96 Input 97 98 ``` 99 6 100 101 + 100 102 103 ? 100 104 105 + 200 106 107 ? 100 108 109 + 50 110 111 ? 50 112 ``` 113 114 Output 115 116 ``` 117 200 118 300 119 150 120 ``` 121 122 Note 123 124 In the first example: 125 126 After the first and second queries, the set will contain elements $\{0, 1, 2\}$. The smallest non-negative number that is divisible by $1$ and is not contained in the set is $3$. 127 128 After the fourth query, the set will contain the elements $\{0, 1, 2, 4\}$. The smallest non-negative number that is divisible by $2$ and is not contained in the set is $6$. 129 130 In the second example: 131 132 * Initially, the set contains only the element $\{0\}$. 133 * After adding an integer $100$ the set contains elements $\{0, 100\}$. 134 * $100\text{-mex}$ of the set is $200$. 135 * After adding an integer $200$ the set contains elements $\{0, 100, 200\}$. 136 * $100\text{-mex}$ of the set is $300$. 137 * After adding an integer $50$ the set contains elements $\{0, 50, 100, 200\}$. 138 * $50\text{-mex}$ of the set is $150$.