2126C.md (2728B)
1 Source: https://codeforces.com/problemset/problem/2126/C 2 3 C. I Will Definitely Make It 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 You are given $n$ towers, numbered from $1$ to $n$. Tower $i$ has a height of $h_i$. At time $0$, you are on the tower with index $k$, and the current water level is $1$. 22 23 Every second, the water level rises by $1$ unit. At any moment, if the water level becomes strictly greater than the height of the tower you are on, you perish. 24 25 You have a magical ability: at moment $x$, you can start teleporting from tower $i$ to tower $j$, which will take $\lvert h_i - h_j \rvert$ seconds. That is, until moment $x + \lvert h_i - h_j \rvert$, you will be on tower $i$, and at moment $x + \lvert h_i - h_j \rvert$, you will move to tower $j$. You can start a new teleportation at the same moment you just arrived at tower $j$. 26 27 For example, if $n=k=4$, $h=[4, 4, 4, 2]$, then if you start teleporting from tower $4$ to tower $1$ at moment $0$, the movement will look as follows: 28 29  30 31 Note that if the height of tower $1$ were $5$, you would not be able to teleport to it immediately, as you would be submerged at moment $2$. 32 33 Your goal is to reach any tower with the maximum height before the water covers you. 34 35 Determine if this is possible. 36 37 Input 38 39 Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 40 41 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the number of towers and the index of the tower you are initially on. 42 43 The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$) — the heights of the towers. 44 45 It is guaranteed that the sum of all $n$ across all test cases does not exceed $10^5$. 46 47 Output 48 49 For each test case, output one line: "YES", if you can reach the tower with the maximum height before the water covers you, or "NO" otherwise. 50 51 You may output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer. 52 53 Example 54 55 Input 56 57 ``` 58 5 59 60 5 3 61 62 3 2 1 4 5 63 64 3 1 65 66 1 3 4 67 68 4 4 69 70 4 4 4 2 71 72 6 2 73 74 2 3 6 9 1 2 75 76 4 2 77 78 1 2 5 6 79 ``` 80 81 Output 82 83 ``` 84 YES 85 NO 86 YES 87 YES 88 NO 89 ``` 90 91 Note 92 93 In the first test case, the only possible path is: $3 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 5$. 94 95 In the second test case, regardless of the order, it will not be possible to reach the tallest tower. 96 97 In the third test case, one of the possible paths is: $4 \rightarrow 1$.