codeforces-scrape

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

1878E.md (2942B)


      1 Source: https://codeforces.com/problemset/problem/1878/E
      2 
      3 E. Iva & Pav
      4 
      5 time limit per test
      6 
      7 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 Iva and Pav are a famous Serbian competitive programming couple. In Serbia, they call Pav "papuca" and that's why he will make all of Iva's wishes come true.
     22 
     23 Iva gave Pav an array $a$ of $n$ elements.
     24 
     25 Let's define $f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$ (here $\&$ denotes the [bitwise AND operation](http://tiny.cc/bitwise_and)).
     26 
     27 Note that $f(l, r)$ is not defined when $l \gt r$.
     28 
     29 Iva also gave Pav $q$ queries.
     30 
     31 Each query consists of 2 numbers, $k$ and $l$, and she wants Pav to find the largest index $r$ ($l \le r \le n$), such that $f(l, r) \ge k$.
     32 
     33 Pav wants to solve this problem fast because he doesn't want to upset Iva. He needs your help.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     38 
     39 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of array $a$.
     40 
     41 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of array $a$.
     42 
     43 The third line of each test case contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries Iva gave Pav.
     44 
     45 The next $q$ lines of each test case contains two numbers, $l$ and $k$ ($1 \le l \le n$, $1 \le k \le 10^9$) — the left bound for the subsegment, and the integer $k$ described in statement.
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. Also, it is guaranteed that the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each query output maximal index $r$ ($l \le r \le n$) such that $a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ \ge \ k$.
     52 
     53 If such $r$ doesn't exist, output $-1$.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 3
     61 
     62 5
     63 
     64 15 14 17 42 34
     65 
     66 3
     67 
     68 1 7
     69 
     70 2 15
     71 
     72 4 5
     73 
     74 5
     75 
     76 7 5 3 1 7
     77 
     78 4
     79 
     80 1 7
     81 
     82 5 7
     83 
     84 2 3
     85 
     86 2 2
     87 
     88 7
     89 
     90 19 20 15 12 21 7 11
     91 
     92 4
     93 
     94 1 15
     95 
     96 4 4
     97 
     98 7 12
     99 
    100 5 7
    101 ```
    102 
    103 Output
    104 
    105 ```
    106 2 -1 5 
    107 1 5 2 2 
    108 2 6 -1 5
    109 ```
    110 
    111 Note
    112 
    113 In the first test case $n=5$, and the array $a = [15, 14, 17, 42, 34]$
    114 
    115 The first query asks for the biggest index $r$ such that the $f(1, r) \ge 7$.
    116 
    117 $f(1,1) = 15, \ f(1, 2) = 14, \ f(1,3)=0 \ f(1, 4)=0 \ f(1, 5)=0$, so $r=2$ is the answer.
    118 
    119 The second query asks for $f(2, r) \ge 15$. Since such $r$ doesn't exist, the answer is $-1$.
    120 
    121 The third query asks for $f(4, r) \ge 5$. $f(4, 4) = 42, \ f(4, 5) = 34$, so $r=5$ is the answer.
    122 
    123 In the second test case $n=5$, and the array $a= [7, 5, 3, 1, 7]$.
    124 
    125 For the first query, $f(1, r) \ge 7$.
    126 
    127 $f(1, 1)=7, \ f(1, 2)=5, \ f(1, 3) = 1, \ f(1,4) = 1, \ f(1, 5)=1$, so the answer to this query is $1$.
    128 
    129 For the second query, $f(5, r) \ge 7$.
    130 
    131 $f(5, 5) = 7$, so the answer is $5$.
    132 
    133 For the third query, $f(2, r) \ge 3$.
    134 
    135 $f(2, 2) = 5, \ f(2, 3) = 1, \ f(2, 4) = 1, \ f(2, 5) = 1$, so the answer is $2$.