- i ued merge sort to sort the x coordinates.
2)then,i took the new sorted array and traversed through each element ,finding the elements for which this condition is satisfied: arr[i+1]-arr[i]>k.i stored these in a new array (let it be p array).
3)now in each query I take in the values of x and y(frog nos),and find their respective positions(x coordinates)…let them be pos(x) and pos(y)…now i go through the “p” array and check if there is any value in it that satisfies this condition:pos(x)<=value<pos(y). if there is such a value the answer is “NO” and “YES” if otherwise.
For example: INPUT:
5 1 1
0 1 5 6 8
2 4
1)here after sorting the array is:0 1 5 6 8
2)in this case my “p” array would contain the elements 1 6…bcoz (5-1>k) and(8-6>k).
- now in the query i have x=2,y=4…pos(2)=1 and pos(4)=6. now there is an element(1) in my p array which satisfies the condition 1<=1<6 and hence my answer would be “NO”.
my time complexity is o(nlogn)…but i am getting tle…is my algo correct??if yes how to resolve the tle issue??
sol link: CodeChef: Practical coding for everyone