2123C.md (2401B)
1 Source: https://codeforces.com/problemset/problem/2123/C 2 3 C. Prefix Min and Suffix Max 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$ of distinct integers. 22 23 In one operation, you may either: 24 25 * choose a nonempty prefix$^{\text{∗}}$ of $a$ and replace it with its minimum value, or 26 * choose a nonempty suffix$^{\text{†}}$ of $a$ and replace it with its maximum value. 27 28 Note that you may choose the entire array $a$. 29 30 For each element $a_i$, determine if there exists some sequence of operations to transform $a$ into $[a_i]$; that is, make the array $a$ consist of only one element, which is $a_i$. Output your answer as a binary string of length $n$, where the $i$-th character is $1$ if there exists a sequence to transform $a$ into $[a_i]$, and $0$ otherwise. 31 32 $^{\text{∗}}$A prefix of an array is a subarray consisting of the first $k$ elements of the array, for some integer $k$. 33 34 $^{\text{†}}$A suffix of an array is a subarray consisting of the last $k$ elements of the array, for some integer $k$. 35 36 Input 37 38 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 39 40 The first line of each test case contains one integer $n$ ($2 \leq n \leq 2\cdot 10^5$) — the size of the array $a$. 41 42 The second line of each test case contains $n$ integers, $a_1,a_2,\dots,a_n$ ($1 \leq a_i \leq 10^6$). It is guaranteed that all $a_i$ are distinct. 43 44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 45 46 Output 47 48 For each test case, output a binary string of length $n$ — the $i$-th character should be $1$ if there exists a sequence of operations as described above, and $0$ otherwise. 49 50 Example 51 52 Input 53 54 ``` 55 3 56 57 6 58 59 1 3 5 4 7 2 60 61 4 62 63 13 10 12 20 64 65 7 66 67 1 2 3 4 5 6 7 68 ``` 69 70 Output 71 72 ``` 73 100011 74 1101 75 1000001 76 ``` 77 78 Note 79 80 In the first sample, you can first choose the prefix of size $3$. Then the array is transformed into 81 82 | | | | | 83 | --- | --- | --- | --- | 84 | 1 | 4 | 7 | 2 | 85 86 Next, you can choose the suffix of size $2$. Then the array is transformed into 87 88 | | | | 89 | --- | --- | --- | 90 | 1 | 4 | 7 | 91 92 Finally, you can choose the prefix of size $3$. Then the array is transformed into 93 94 | | 95 | --- | 96 | 1 | 97 98 So we see that it is possible to transform $a$ into $[1]$. 99 100 It can be shown that it is impossible to transform $a$ into $[3]$.