codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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