codeforces-scrape

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

1843E.md (2646B)


      1 Source: https://codeforces.com/problemset/problem/1843/E
      2 
      3 E. Tracking Segments
      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 You are given an array $a$ consisting of $n$ zeros. You are also given a set of $m$ not necessarily different segments. Each segment is defined by two numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) and represents a subarray $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ of the array $a$.
     22 
     23 Let's call the segment $l_i, r_i$ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $a = [1, 0, 1, 0, 1]$, then the segment $[1, 5]$ is beautiful (the number of ones is $3$, the number of zeros is $2$), but the segment $[3, 4]$ is not is beautiful (the number of ones is $1$, the number of zeros is $1$).
     24 
     25 You also have $q$ changes. For each change you are given the number $1 \le x \le n$, which means that you must assign an element $a_x$ the value $1$.
     26 
     27 You have to find the first change after which at least one of $m$ given segments becomes beautiful, or report that none of them is beautiful after processing all $q$ changes.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains two integers $n$ and $m$ ($1 \le m \le n \le 10^5$) — the size of the array $a$ and the number of segments, respectively.
     34 
     35 Then there are $m$ lines consisting of two numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) —the boundaries of the segments.
     36 
     37 The next line contains an integer $q$ ($1 \le q \le n$) — the number of changes.
     38 
     39 The following $q$ lines each contain a single integer $x$ ($1 \le x \le n$) — the index of the array element that needs to be set to $1$. It is guaranteed that indexes in queries are distinct.
     40 
     41 It is guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.
     42 
     43 Output
     44 
     45 For each test case, output one integer  — the minimum change number after which at least one of the segments will be beautiful, or $-1$ if none of the segments will be beautiful.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 
     54 5 5
     55 
     56 1 2
     57 
     58 4 5
     59 
     60 1 5
     61 
     62 1 3
     63 
     64 2 4
     65 
     66 5
     67 
     68 5
     69 
     70 3
     71 
     72 1
     73 
     74 2
     75 
     76 4
     77 
     78 4 2
     79 
     80 1 1
     81 
     82 4 4
     83 
     84 2
     85 
     86 2
     87 
     88 3
     89 
     90 5 2
     91 
     92 1 5
     93 
     94 1 5
     95 
     96 4
     97 
     98 2
     99 
    100 1
    101 
    102 3
    103 
    104 4
    105 
    106 5 2
    107 
    108 1 5
    109 
    110 1 3
    111 
    112 5
    113 
    114 4
    115 
    116 1
    117 
    118 2
    119 
    120 3
    121 
    122 5
    123 
    124 5 5
    125 
    126 1 5
    127 
    128 1 5
    129 
    130 1 5
    131 
    132 1 5
    133 
    134 1 4
    135 
    136 3
    137 
    138 1
    139 
    140 4
    141 
    142 3
    143 
    144 3 2
    145 
    146 2 2
    147 
    148 1 3
    149 
    150 3
    151 
    152 2
    153 
    154 3
    155 
    156 1
    157 ```
    158 
    159 Output
    160 
    161 ```
    162 3
    163 -1
    164 3
    165 3
    166 3
    167 1
    168 ```
    169 
    170 Note
    171 
    172 In the first case, after first 2 changes we won't have any beautiful segments, but after the third one on a segment $[1; 5]$ there will be 3 ones and only 2 zeros, so the answer is 3.
    173 
    174 In the second case, there won't be any beautiful segments.