HostelVisit(2nd TestCase TLE)

#1

Second TestCase Showing Time Limit: What is wrong?): https://ide.codingblocks.com/s/104504

#2

@anushkasharma1108
As you can see the constraints mentioned in the question are large and your code runs in roughly O(qk) time complexity where q is the total number of queries and k is as specified in the problem.
Your approach while correct , takes a lot of time to process and thus gives TLE.
There’s a faster approach for this question that takes O(q log k) time.

Create a max heap of size k. Store only atmost k elements in it. If you get a new element , compare it with the top of the heap and if the new element is lesser than pq.top() then pop one element from the heap and push one more thus maintaining the size = k .
If you get a query of type 2 where you have to print the kth distance , simply print pq.top() since the heap is already of size k and we are only storing the smaller values in it.
Try this approach and let me know if you face any problems with it.

1 Like
#3

https://ide.codingblocks.com/s/104504 I have changed the code but now it is showing wrong answer for the 2nd test case

#4

@anushkasharma1108
As you can see , the values of the coordinates can be as large as 10^6. Since the distance is formed by taking the sum of their products , the value of distance is bound to cross the range of int.
Use long long int instead of int in your entire program and it will work fine.

1 Like