2036E.md (4459B)
1 Source: https://codeforces.com/problemset/problem/2036/E 2 3 E. Reverse the Rivers 4 5 time limit per test 6 7 2 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 A conspiracy of ancient sages, who decided to redirect rivers for their own convenience, has put the world on the brink. But before implementing their grand plan, they decided to carefully think through their strategy — that's what sages do. 22 23 There are $n$ countries, each with exactly $k$ regions. For the $j$-th region of the $i$-th country, they calculated the value $a_{i,j}$, which reflects the amount of water in it. 24 25 The sages intend to create channels between the $j$-th region of the $i$-th country and the $j$-th region of the $(i + 1)$-th country for all $1 \leq i \leq (n - 1)$ and for all $1 \leq j \leq k$. 26 27 Since all $n$ countries are on a large slope, water flows towards the country with the highest number. According to the sages' predictions, after the channel system is created, the new value of the $j$-th region of the $i$-th country will be $b_{i,j} = a_{1,j} | a_{2,j} | ... | a_{i,j}$, where $|$ denotes the [bitwise "OR"](http://tiny.cc/bitwise_or) operation. 28 29 After the redistribution of water, the sages aim to choose the most suitable country for living, so they will send you $q$ queries for consideration. 30 31 Each query will contain $m$ requirements. 32 33 Each requirement contains three parameters: the region number $r$, the sign $o$ (either "$ \lt $" or "$ \gt $"), and the value $c$. If $o$ = "$ \lt $", then in the $r$-th region of the country you choose, the new value must be strictly less than the limit $c$, and if $o$ = "$ \gt $", it must be strictly greater. 34 35 In other words, the chosen country $i$ must satisfy all $m$ requirements. If in the current requirement $o$ = "$ \lt $", then it must hold that $b_{i,r} \lt c$, and if $o$ = "$ \gt $", then $b_{i,r} \gt c$. 36 37 In response to each query, you should output a single integer — the number of the suitable country. If there are multiple such countries, output the smallest one. If no such country exists, output $-1$. 38 39 Input 40 41 The first line contains three integers $n$, $k$, and $q$ ($1 \leq n, k, q \leq 10^5$) — the number of countries, regions, and queries, respectively. 42 43 Next, there are $n$ lines, where the $i$-th line contains $k$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ ($1 \leq a_{i,j} \leq 10^9$), where $a_{i,j}$ is the value of the $j$-th region of the $i$-th country. 44 45 Then, $q$ queries are described. 46 47 The first line of each query contains a single integer $m$ ($1 \leq m \leq 10^5$) — the number of requirements. 48 49 Then follow $m$ lines, each containing an integer $r$, a character $o$, and an integer $c$ ($1 \leq r \leq k$, $0 \leq c \leq 2 \cdot 10^9$), where $r$ and $c$ are the region number and the value, and $o$ is either "$ \lt $" or "$ \gt $" — the sign. 50 51 It is guaranteed that $n \cdot k$ does not exceed $10^5$ and that the sum of $m$ across all queries also does not exceed $10^5$. 52 53 Output 54 55 For each query, output a single integer on a new line — the smallest number of the suitable country, or $-1$ if no such country exists. 56 57 Example 58 59 Input 60 61 ``` 62 3 4 4 63 64 1 3 5 9 65 66 4 6 5 3 67 68 2 1 2 7 69 70 3 71 72 1 > 4 73 74 2 < 8 75 76 1 < 6 77 78 2 79 80 1 < 8 81 82 2 > 8 83 84 1 85 86 3 > 5 87 88 2 89 90 4 > 8 91 92 1 < 8 93 ``` 94 95 Output 96 97 ``` 98 2 99 -1 100 3 101 1 102 ``` 103 104 Note 105 106 In the example, the initial values of the regions are as follows: 107 108 | | | | | 109 | --- | --- | --- | --- | 110 | $1$ | $3$ | $5$ | $9$ | 111 | $4$ | $6$ | $5$ | $3$ | 112 | $2$ | $1$ | $2$ | $7$ | 113 114 After creating the channels, the new values will look like this: 115 116 | | | | | 117 | --- | --- | --- | --- | 118 | $1$ | $3$ | $5$ | $9$ | 119 | $1 | 4$ | $3 | 6$ | $5 | 5$ | $9 | 3$ | 120 | $1 | 4 | 2$ | $3 | 6 | 1$ | $5 | 5 | 2$ | $9 | 3 | 7$ | 121 122 $\downarrow$ 123 124 | | | | | 125 | --- | --- | --- | --- | 126 | $1$ | $3$ | $5$ | $9$ | 127 | $5$ | $7$ | $5$ | $11$ | 128 | $7$ | $7$ | $7$ | $15$ | 129 130 In the first query, it is necessary to output the minimum country number (i.e., row) where, after the redistribution of water in the first region (i.e., column), the new value will be greater than four and less than six, and in the second region it will be less than eight. Only the country with number $2$ meets these requirements. 131 132 In the second query, there are no countries that meet the specified requirements. 133 134 In the third query, only the country with number $3$ is suitable. 135 136 In the fourth query, all three countries meet the conditions, so the answer is the smallest number $1$.