codeforces-scrape

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

1023D.md (3048B)


      1 Source: https://codeforces.com/problemset/problem/1023/D
      2 
      3 D. Array Restoration
      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 Initially there was an array $a$ consisting of $n$ integers. Positions in it are numbered from $1$ to $n$.
     22 
     23 Exactly $q$ queries were performed on the array. During the $i$-th query some segment $(l_i, r_i)$ $(1 \le l_i \le r_i \le n)$ was selected and values of elements on positions from $l_i$ to $r_i$ inclusive got changed to $i$. The order of the queries couldn't be changed and all $q$ queries were applied. It is also known that every position from $1$ to $n$ got covered by at least one segment.
     24 
     25 We could have offered you the problem about checking if some given array (consisting of $n$ integers with values from $1$ to $q$) can be obtained by the aforementioned queries. However, we decided that it will come too easy for you.
     26 
     27 So the enhancement we introduced to it is the following. Some set of positions (possibly empty) in this array is selected and values of elements on these positions are set to $0$.
     28 
     29 Your task is to check if this array can be obtained by the aforementioned queries. Also if it can be obtained then restore this array.
     30 
     31 If there are multiple possible arrays then print any of them.
     32 
     33 Input
     34 
     35 The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of elements of the array and the number of queries perfomed on it.
     36 
     37 The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le q$) — the resulting array. If element at some position $j$ is equal to $0$ then the value of element at this position can be any integer from $1$ to $q$.
     38 
     39 Output
     40 
     41 Print "YES" if the array $a$ can be obtained by performing $q$ queries. Segments $(l_i, r_i)$ $(1 \le l_i \le r_i \le n)$ are chosen separately for each query. Every position from $1$ to $n$ should be covered by at least one segment.
     42 
     43 Otherwise print "NO".
     44 
     45 If some array can be obtained then print $n$ integers on the second line — the $i$-th number should be equal to the $i$-th element of the resulting array and should have value from $1$ to $q$. This array should be obtainable by performing exactly $q$ queries.
     46 
     47 If there are multiple possible arrays then print any of them.
     48 
     49 Examples
     50 
     51 Input
     52 
     53 ```
     54 4 3  
     55 1 0 2 3
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 YES  
     62 1 2 2 3
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 3 10  
     69 10 10 10
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 YES  
     76 10 10 10
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 5 6  
     83 6 5 6 2 2
     84 ```
     85 
     86 Output
     87 
     88 ```
     89 NO
     90 ```
     91 
     92 Input
     93 
     94 ```
     95 3 5  
     96 0 0 0
     97 ```
     98 
     99 Output
    100 
    101 ```
    102 YES  
    103 5 4 2
    104 ```
    105 
    106 Note
    107 
    108 In the first example you can also replace $0$ with $1$ but not with $3$.
    109 
    110 In the second example it doesn't really matter what segments to choose until query $10$ when the segment is $(1, 3)$.
    111 
    112 The third example showcases the fact that the order of queries can't be changed, you can't firstly set $(1, 3)$ to $6$ and after that change $(2, 2)$ to $5$. The segment of $5$ should be applied before segment of $6$.
    113 
    114 There is a lot of correct resulting arrays for the fourth example.