codeforces-scrape

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

1927D.md (2200B)


      1 Source: https://codeforces.com/problemset/problem/1927/D
      2 
      3 D. Find the Different Ones!
      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 You are given an array $a$ of $n$ integers, and $q$ queries.
     22 
     23 Each query is represented by two integers $l$ and $r$ ($1 \le l \le r \le n$). Your task is to find, for each query, two indices $i$ and $j$ (or determine that they do not exist) such that:
     24 
     25 * $l \le i \le r$;
     26 * $l \le j \le r$;
     27 * $a_i \ne a_j$.
     28 
     29 In other words, for each query, you need to find a pair of different elements among $a_l, a_{l+1}, \dots, a_r$, or report that such a pair does not exist.
     30 
     31 Input
     32 
     33 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The descriptions of the test cases follow.
     34 
     35 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array $a$.
     38 
     39 The third line of each test case contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.
     40 
     41 The next $q$ lines contain two integers each, $l$ and $r$ ($1 \le l \lt r \le n$) — the boundaries of the query.
     42 
     43 It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of the values of $q$ across all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each query, output two integers separated by space: $i$ and $j$ ($l \le i, j \le r$), for which $a_i \ne a_j$. If such a pair does not exist, output $i=-1$ and $j=-1$.
     48 
     49 You may separate the outputs for the test cases with empty lines. This is not a mandatory requirement.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 5
     57 
     58 5
     59 
     60 1 1 2 1 1
     61 
     62 3
     63 
     64 1 5
     65 
     66 1 2
     67 
     68 1 3
     69 
     70 6
     71 
     72 30 20 20 10 10 20
     73 
     74 5
     75 
     76 1 2
     77 
     78 2 3
     79 
     80 2 4
     81 
     82 2 6
     83 
     84 3 5
     85 
     86 4
     87 
     88 5 2 3 4
     89 
     90 4
     91 
     92 1 2
     93 
     94 1 4
     95 
     96 2 3
     97 
     98 2 4
     99 
    100 5
    101 
    102 1 4 3 2 4
    103 
    104 5
    105 
    106 1 5
    107 
    108 2 4
    109 
    110 3 4
    111 
    112 3 5
    113 
    114 4 5
    115 
    116 5
    117 
    118 2 3 1 4 2
    119 
    120 7
    121 
    122 1 2
    123 
    124 1 4
    125 
    126 1 5
    127 
    128 2 4
    129 
    130 2 5
    131 
    132 3 5
    133 
    134 4 5
    135 ```
    136 
    137 Output
    138 
    139 ```
    140 2 3
    141 -1 -1
    142 1 3
    143 
    144 2 1
    145 -1 -1
    146 4 2
    147 4 6
    148 5 3
    149 
    150 1 2
    151 1 2
    152 2 3
    153 3 2
    154 
    155 1 3
    156 2 4
    157 3 4
    158 5 3
    159 5 4
    160 
    161 1 2
    162 4 2
    163 1 3
    164 2 3
    165 3 2
    166 5 4
    167 5 4
    168 ```