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