FRoGV HELP

  1. 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).

  1. 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: http://www.codechef.com/viewsolution/4319695

try this:

your code does not show output for query :6 10

10 3 3

0 3 8 5 12 15 17 22 24 27

can u specify the input according to the format mentioned in the prob…i couldnt understand it…

10 3 3

0 3 8 5 12 15 17 22 24 27

1 5

1 6

6 10

your code does not show anything for last query

as you have pointed ,it is not showing any output for last query when compiled in ideone…http://ideone.com/cxYExE...it is showing time limit exceeded…but when compiled in dev c++ in my system, it is giving correct output as “No”.why is it showing tle in ideone??

why does it show tle in ideone whereas it compiles correctly in my pc for the above case??

your processor way faster than those of online judges.that is why you get tle.

but still i think my complexity is O(nlogn)…and online judges inspite being slower should not have a prob with it…