codeforces-scrape

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

2152C.md (3233B)


      1 Source: https://codeforces.com/problemset/problem/2152/C
      2 
      3 C. Triple Removal
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Tired of supporting ranged carries, Keria is now creating a data structure problem about supporting range queries.
     22 
     23 For an array $b = [b_1, b_2, \ldots, b_m]$ of length $m$ where $b_i=0$ or $b_i=1$, consider the following triple removal operation:
     24 
     25 1. Choose three indices $1 \le i \lt j \lt k \le m$ such that the elements at these positions are identical ($b_i = b_j = b_k$).
     26 2. Remove these three elements from the array. The cost of this operation is defined as $\min(k-j, j-i)$. After the removal, the remaining parts of the array are concatenated, and their indices are relabeled.
     27 
     28 We want to make the array $b$ empty using the triple removal operation. Hence, we define the total cost of an array as the minimum possible sum of the costs of triple removal operations required to make the array empty. If it is impossible to make the array empty, the cost is defined to be $-1$.
     29 
     30 Keria wants to test his data structure. For this, you must answer $q$ independent queries. Initially, you are given an array $a = [a_1, a_2, \ldots, a_n]$ of length $n$ where $a_i=0$ or $a_i=1$. For each query, you are given a range $1 \le l \le r \le n$ and must find the cost for the array $[a_l, a_{l+1}, \ldots, a_r]$.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     35 
     36 The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 250\,000$) — the length of the array and the number of queries.
     37 
     38 The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = 0$ or $a_i=1$) — the elements of the array.
     39 
     40 Then $q$ lines follow. The $i$-th of them contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the range of the subarray for the $i$-th query.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $250\,000$.
     43 
     44 It is guaranteed that the sum of $q$ over all test cases does not exceed $250\,000$.
     45 
     46 Output
     47 
     48 For each test case, output $q$ lines. The $i$-th line should contain a single integer representing the answer to the $i$-th query.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 2
     56 
     57 12 4
     58 
     59 0 0 1 1 0 1 0 1 0 1 1 0
     60 
     61 1 12
     62 
     63 2 7
     64 
     65 5 10
     66 
     67 6 11
     68 
     69 6 3
     70 
     71 0 0 0 1 1 1
     72 
     73 1 3
     74 
     75 4 6
     76 
     77 1 6
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 4
     84 
     85 2
     86 
     87 3
     88 
     89 -1
     90 
     91 1
     92 
     93 1
     94 
     95 2
     96 ```
     97 
     98 Note
     99 
    100 Explanation of the first test case, first query (1 12):
    101 
    102 The subarray is $[0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]$. There are six $0$s and six $1$s. A possible optimal sequence of operations is:
    103 
    104 1. Remove the three $1$s at indices $3$, $4$, $6$. The cost is $\min(6-4, 4-3) = \min(2, 1) = 1$. The array becomes $[0, 0, 0, 0, 1, 0, 1, 1, 0]$.
    105 2. Remove the three $0$s at indices $1$, $2$, $3$. The cost is $\min(3-2, 2-1) = \min(1, 1) = 1$. The array becomes $[0, 1, 0, 1, 1, 0]$.
    106 3. Remove the three $1$s at indices $2$, $4$, $5$. The cost is $\min(5-4, 4-2) = \min(1, 2) = 1$. The array becomes $[0, 0, 0]$.
    107 4. Remove the three $0$s at indices $1$, $2$, $3$. The cost is $\min(3-2, 2-1) = \min(1, 1) = 1$. The array is now empty.
    108 
    109 The total cost is $1+1+1+1=4$.