2157C.md (2903B)
1 Source: https://codeforces.com/problemset/problem/2157/C 2 3 C. Meximum Array 2 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 [Ferus Melek - Brute Force](https://soundcloud.com/ferusmelek/brute-force) 22 23 ⠀ 24 25 You are given three positive integers $n$, $k$, and $q$. You are also given $q$ tuples $(c, l, r)$, with $1 \leq c \leq 2$ and $1 \leq l \leq r \leq n$. 26 27 An array $a_1, a_2, \ldots, a_n$ is meximum if $0 \leq a_i \leq 10^9$ for each $i$ in $[1, n]$, and for each given tuple $(c, l, r)$, 28 29 * if $c = 1$, then $\min(a_l, a_{l+1}, \ldots, a_r) = k$; 30 * if $c = 2$, then $\operatorname{MEX}$$^{\text{∗}}$$(a_l, a_{l+1}, \ldots, a_r) = k$. 31 32 Note that the parameter $k$ is the same for all the conditions. 33 34 Find a meximum array $a_1, a_2, \ldots, a_n$ of length $n$. The input is generated in such a way that a valid array always exists. If there are multiple possible arrays, you can print any one of them. 35 36 $^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $a_1, a_2, \ldots, a_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $a$. 37 38 Input 39 40 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows. 41 42 The first line of each test case contains three integers $n$, $k$, $q$ ($1 \leq k \leq n \leq 100$, $1 \leq q \leq 100$) — the length of the array $a_1, a_2, \ldots, a_n$, the result of the $\min$ and $\operatorname{MEX}$ calculations described by the tuples, and the number of tuples. 43 44 Then, $q$ lines follow. The $i$-th line contains a tuple $(c, l, r)$, which gives a constraint to $a_l, a_{l+1}, \ldots, a_r$ according to the statement. 45 46 It is guaranteed that there exists a valid array corresponding to the given input. 47 48 Note that there are no constraints on the sum of $n$, $k$, or $q$ over all test cases. 49 50 Output 51 52 For each test case, print a single line containing a meximum array $a_1, a_2, \ldots, a_n$. 53 54 Example 55 56 Input 57 58 ``` 59 4 60 61 6 2 2 62 63 1 1 3 64 65 2 2 6 66 67 3 3 1 68 69 2 1 3 70 71 3 3 2 72 73 1 1 1 74 75 1 3 3 76 77 3 2 2 78 79 2 1 2 80 81 2 2 3 82 ``` 83 84 Output 85 86 ``` 87 2 5 4 3 0 1 88 2 0 1 89 3 3 3 90 1 0 1 91 ``` 92 93 Note 94 95 In the first test case, you have to build a meximum array with $n = 6$, $k = 2$ and with $q = 2$ constraints given by tuples. 96 97 * tuple $(1, 1, 3)$: $\min(a_1, a_2, a_3)$ must be $2$; 98 * tuple $(2, 2, 6)$: $\operatorname{MEX}(a_2, a_3, a_4, a_5, a_6)$ must be $2$. 99 100 A possible array that satisfies all these constraints, and has elements $0 \leq a_i \leq 10^9$, is $[2, 5, 4, 3, 0, 1]$. 101 102 In the second test case, you have to build a meximum array with $n = 3$, $k = 3$ and with $q = 1$ constraint given by a tuple. 103 104 * tuple $(2, 1, 3)$: $\operatorname{MEX}(a_1, a_2, a_3)$ must be $3$. 105 106 A possible array that satisfies this constraint, and has elements $0 \leq a_i \leq 10^9$, is $[2, 0, 1]$.