1870C.md (2462B)
1 Source: https://codeforces.com/problemset/problem/1870/C 2 3 C. Colorful Table 4 5 time limit per test 6 7 1 second 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 two integers $n$ and $k$. You are also given an array of integers $a_1, a_2, \ldots, a_n$ of size $n$. It is known that for all $1 \leq i \leq n$, $1 \leq a_i \leq k$. 22 23 Define a two-dimensional array $b$ of size $n \times n$ as follows: $b_{i, j} = \min(a_i, a_j)$. Represent array $b$ as a square, where the upper left cell is $b_{1, 1}$, rows are numbered from top to bottom from $1$ to $n$, and columns are numbered from left to right from $1$ to $n$. Let the color of a cell be the number written in it (for a cell with coordinates $(i, j)$, this is $b_{i, j}$). 24 25 For each color from $1$ to $k$, find the smallest rectangle in the array $b$ containing all cells of this color. Output the sum of width and height of this rectangle. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follows the description of the test cases. 30 31 The first line of each test case contains two integers $n$ and $k$ ($1 \leq n, k \leq 10^5$) — the size of array $a$ and the number of colors. 32 33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq k$) — the array $a$. 34 35 It is guaranteed that the sum of the values of $n$ and $k$ over all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, output $k$ numbers: the sums of width and height of the smallest rectangle containing all cells of a color, for each color from $1$ to $k$. 40 41 Example 42 43 Input 44 45 ``` 46 5 47 48 2 1 49 50 1 1 51 52 2 2 53 54 1 2 55 56 3 5 57 58 3 2 4 59 60 4 2 61 62 1 2 1 2 63 64 5 3 65 66 1 2 3 2 1 67 ``` 68 69 Output 70 71 ``` 72 4 73 4 2 74 0 6 6 2 0 75 8 6 76 10 6 2 77 ``` 78 79 Note 80 81 In the first test case, the entire array $b$ consists of color $1$, so the smallest rectangle for color $1$ has a size of $2 \times 2$, and the sum of its sides is $4$. 82 83 In the second test case, the array $b$ looks like this: 84 85 | | | 86 | --- | --- | 87 | 1 | 1 | 88 | 1 | 2 | 89 90 One of the corner cells has color $2$, and the other three cells have color $1$. Therefore, the smallest rectangle for color $1$ has a size of $2 \times 2$, and for color $2$ it is $1 \times 1$. 91 92 In the last test case, the array $b$ looks like this: 93 94 | | | | | | 95 | --- | --- | --- | --- | --- | 96 | 1 | 1 | 1 | 1 | 1 | 97 | 1 | 2 | 2 | 2 | 1 | 98 | 1 | 2 | 3 | 2 | 1 | 99 | 1 | 2 | 2 | 2 | 1 | 100 | 1 | 1 | 1 | 1 | 1 |