ADAPLANT - Ada and Plants
Ada the Ladybug has grown many plants. She was trying to grow all plants with equal size. Now she is wondering about the biggest difference between heights of two plants which are near each other. Plants are near each other, if there are at most K plants between them.
Input
The first line contains T, the number of test-cases. The first line of each test-case will contain N, K, 1 < N ≤ 105 ,0 ≤ K ≤ 105 where N indicates number of plants.Next line will contain N integers 0 ≤ hi ≤ 109 indicating height of i-th plant.
Sum of all N among all test-cases won't exceed 3*106
Output
For each test-case, print exactly one number - the biggest difference of plants near each other (biggest hi-hj such that |i-j|-1 ≤ K).Example Input
3 5 0 1 2 3 5 6 4 6 1 10 2 9 10 1 1 7 8 9 19 11 21 8 11 0
Example Output
2 9 13
hide comments
|
ayu_031201:
2022-04-25 17:13:21
Use Multiset and a kind of sliding window concept |
|
hsraktu:
2018-10-13 23:37:26
can use multiset or 2 deque for max and min for every [i....i+k+1] range |
|
learnerinblack:
2018-05-24 08:33:37
@morass I am trying to solve this by square root decomposition method(time complexity O(sqrt(N)*N) - correct me if i am wrong) but I don't know why it is giving wrong answer after test case 10. I am new to this concept so it would be of great help if you could point out my mistake
|
|
julkas:
2017-10-29 16:11:44
Different approach PQ. Last edit: 2017-10-30 09:21:49 |
|
shahzada:
2017-03-24 06:47:30
Easy segment tree. |
|
morass:
2016-09-13 14:55:15
@rajat_kumar: Hi, maybe I've looked badly, but your algo seems N*K to me (so if I'm not wrong, then you have to improve algorithm :'( ) |
|
rajat_kumar:
2016-09-08 13:04:21
@morass can you please look at my code and tell if i am getting TLE due to lack of optimisation or a faulty algo,:(
|
|
|
morass:
2016-09-07 23:35:06
@ivo2001: Mistake was in statement! Thank you for pointing out! :) |
|
ivo2001:
2016-09-07 23:04:28
In the statement is written that N and K will be bigger than 1, but in the first sample K is equal to 0 is the mistake in the statement or in the sample? |
| Added by: | Morass |
| Date: | 2016-09-05 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU |
RSS