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.