codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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