Anyone who codes in java can implement the solution given in editorial using TreeMap.
Refer my code
https://www.codechef.com/viewsolution/18603460
@vijju123, the value of âdâ doesnât matter. Let LHS = 3 - d. we want to want LHS >= something. So, if something = 9 satisfies it, so does 7. After this try to see the construction of temp array for example in the editorial. Then things would be clear.
1 Like
OhâŚI was taking 9 in LHS instead of taking it in âsomethingâ. Thanks. I will re-read,re-check and re-analyse tomorrow morning and get back to you 
1 Like
@bilalakil check this input :
2
5 5
1 2 3 1 -5
6 6
-1 -2 -3 3 3 -5
your output:
2
-1
correct output:
2
2
@beginner_1111
Can you tell why my solution gives WA.It is giving same ans for above input
Solution Link :
https://www.codechef.com/viewsolution/16654650
Your solution gives â-1â for
1
5 4
-1 1 1 1 1
but the right answer is 4.
1 Like
thanks for test case
please reply!
Divide and Conquer
1 Like
@ksmukta, in this problem we canât apply binary or ternary search on the prefix array directly as it doesnât follow the corresponding properties. One way is to do binary search with segment trees which will also pass but it is theoretically slower. Thus, we tried to see if we can deduce something about the array so that if we get an answer for some index, we could try and reduce something about other indices. These type of observations sometimes leads us to building some array (here called the temporary array) and also reduce complexity as well in some cases.