1706B.md (3069B)
1 Source: https://codeforces.com/problemset/problem/1706/B 2 3 B. Making Towers 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 have a sequence of $n$ colored blocks. The color of the $i$-th block is $c_i$, an integer between $1$ and $n$. 22 23 You will place the blocks down in sequence on an infinite coordinate grid in the following way. 24 25 1. Initially, you place block $1$ at $(0, 0)$. 26 2. For $2 \le i \le n$, if the $(i - 1)$-th block is placed at position $(x, y)$, then the $i$-th block can be placed at one of positions $(x + 1, y)$, $(x - 1, y)$, $(x, y + 1)$ (but not at position $(x, y - 1)$), as long no previous block was placed at that position. 27 28 A tower is formed by $s$ blocks such that they are placed at positions $(x, y), (x, y + 1), \ldots, (x, y + s - 1)$ for some position $(x, y)$ and integer $s$. The size of the tower is $s$, the number of blocks in it. A tower of color $r$ is a tower such that all blocks in it have the color $r$. 29 30 For each color $r$ from $1$ to $n$, solve the following problem independently: 31 32 * Find the maximum size of a tower of color $r$ that you can form by placing down the blocks according to the rules. 33 34 Input 35 36 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 37 38 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$). 39 40 The second line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$). 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, output $n$ integers. The $r$-th of them should be the maximum size of an tower of color $r$ you can form by following the given rules. If you cannot form any tower of color $r$, the $r$-th integer should be $0$. 47 48 Example 49 50 Input 51 52 ``` 53 6 54 55 7 56 57 1 2 3 1 2 3 1 58 59 6 60 61 4 2 2 2 4 4 62 63 1 64 65 1 66 67 5 68 69 5 4 5 3 5 70 71 6 72 73 3 3 3 1 3 3 74 75 8 76 77 1 2 3 4 4 3 2 1 78 ``` 79 80 Output 81 82 ``` 83 3 2 2 0 0 0 0 84 0 3 0 2 0 0 85 1 86 0 0 1 1 1 87 1 0 4 0 0 0 88 2 2 2 2 0 0 0 0 89 ``` 90 91 Note 92 93 In the first test case, one of the possible ways to form a tower of color $1$ and size $3$ is: 94 95 * place block $1$ at position $(0, 0)$; 96 * place block $2$ to the right of block $1$, at position $(1, 0)$; 97 * place block $3$ above block $2$, at position $(1, 1)$; 98 * place block $4$ to the left of block $3$, at position $(0, 1)$; 99 * place block $5$ to the left of block $4$, at position $(-1, 1)$; 100 * place block $6$ above block $5$, at position $(-1, 2)$; 101 * place block $7$ to the right of block $6$, at position $(0, 2)$. 102 103  104 105 The blocks at positions $(0, 0)$, $(0, 1)$, and $(0, 2)$ all have color $1$, forming an tower of size $3$. 106 107 In the second test case, note that the following placement is not valid, since you are not allowed to place block $6$ under block $5$: 108 109  110 111 It can be shown that it is impossible to form a tower of color $4$ and size $3$.