Can’t we solve COOK82C problem using heap, as construction of heap takes nlong(n) time while heapify in worst case takes log(n) time. So looking at the constraint it seems that it can be solved using heap, but it gives tle. Can any one please tell me where i’m going wrong
Thank You
If you use heap, you will delete the top element of max-heap many times ,in fact it will be around max(q[i]) (for each valid i) which can go around 2^{63} , I think that’s the reason.
Q[i] is not upto {2}^{63} , else the queue approach in editorial wont work either xD. The editorial says that heap doesnt work due to logN factor.
Heap should ideally pass, but the setter and tester did not want that. They wanted solutions using queues to pass, hence they set the Time Limit such that heap gets TLE. However, I think you can squeeze your solution via some constant optimizations. Give it a try, on how can your code be improved.
PS: Maximum value of query can be upto {10}^{7} I guess?