@admin: How a solution gets complete AC when it takes 3.74 sec for some test cases and written in Java? What is the time limit for this problem for JAVA?
Solution of Another Solution mentioned in Editorial.
Just Instead of Two heaps I maintained one Max Heap and one Array. I got AC in 0.58 seconds.
I passed the testcases using a persistent segment tree to know the value of the kth element in a range [l,r]. Each query takes log2(N), so passes all the testcases in N * N * log2(N). Nice question if you want to learn different methods to find the kth element in range [l,r] in different complexities. I referred Merge Sort Tree, Order Statistics Tree, and an old Codeforces blog. Beautiful problem
I used the Persistence segment tree for finding kth smallest element. Is this is what the editorial is talking about?
what is the use of TREEOFFSET there in the tester solution? will anyone, please explain to me. thanks in advance
someone, please give the links of the resources of
- finding kth smallest element in an array for a range
- frequency find in a range
I applied the last approach of Heap using priority queue. Can anyone tell me where I was going wrong?
I maintained an array throughout the problem and used insertion sort and tweaked a bit of binary search to find the position to insert an element. once array is sorted, everything will be easy.
Got an AC hahah
Have a look here solution
Why am I unable to add a comment to other users’ answers?
It will be really helpful if anybody could assist me where I am going wrong?
I have used pbds approach.
link to solution:-https://www.codechef.com/viewsolution/23641513
PBDS and fenwick tree also works
can’t believe 4 star user caught in plagiarism
as it was an easy problem… its neither cake walk nor medium according to codechef standards or admin’s/editorialist’s standards…
exactly… I did binary search over BIT…
Both your solutions are really nice, @taran_1407. I could only think of a solution using a Fenwick tree.
it’s a kind of balanced binary search tree afaik…
you can consider it as a black box which does these operations in O(logn)
Then that standard needs to be rectified.