codeforces-scrape

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

928B.md (2662B)


      1 Source: https://codeforces.com/problemset/problem/928/B
      2 
      3 B. Chat
      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 There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago.
     22 
     23 More formal, your message history is a sequence of messages ordered by time sent numbered from 1 to *n* where *n* is the total number of messages in the chat.
     24 
     25 Each message might contain a link to an earlier message which it is a reply to. When opening a message *x* or getting a link to it, the dialogue is shown in such a way that *k* previous messages, message *x* and *k* next messages are visible (with respect to message *x*). In case there are less than *k* messages somewhere, they are yet all shown.
     26 
     27 Digging deep into your message history, you always read all visible messages and then go by the link in the current message *x* (if there is one) and continue reading in the same manner.
     28 
     29 Determine the number of messages you'll read if your start from message number *t* for all *t* from 1 to *n*. Calculate these numbers independently. If you start with message *x*, the initial configuration is *x* itself, *k* previous and *k* next messages. Messages read multiple times are considered as one.
     30 
     31 Input
     32 
     33 The first line contains two integers *n* and *k* (1 ≤ *n* ≤ 105, 0 ≤ *k* ≤ *n*) — the total amount of messages and the number of previous and next messages visible.
     34 
     35 The second line features a sequence of integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* < *i*), where *a**i* denotes the *i*-th message link destination or zero, if there's no link from *i*. All messages are listed in chronological order. It's guaranteed that the link from message *x* goes to message with number strictly less than *x*.
     36 
     37 Output
     38 
     39 Print *n* integers with *i*-th denoting the number of distinct messages you can read starting from message *i* and traversing the links while possible.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 6 0  
     47 0 1 1 2 3 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 1 2 2 3 3 3
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 10 1  
     60 0 1 0 3 4 5 2 3 7 0
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 2 3 3 4 5 6 6 6 8 2
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 2 2  
     73 0 1
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 2 2
     80 ```
     81 
     82 Note
     83 
     84 Consider *i* = 6 in sample case one. You will read message 6, then 2, then 1 and then there will be no link to go.
     85 
     86 In the second sample case *i* = 6 gives you messages 5, 6, 7 since *k* = 1, then 4, 5, 6, then 2, 3, 4 and then the link sequence breaks. The number of distinct messages here is equal to 6.