I have a multiset . Using a loop I am inserting elements. In each loop , I am asked to access n th element of the multiset . where n is increasing in ascending order,1,2,3,4
I used iterator and pointed it to the begin. But for every loop , I have to iterate . This gives me TLE.
Is there any process for fast accessing in multiset ??
I don't know any function or method to do that, but I have a suggestion for that in O(logM * logM) where M is size of the multiset:
use binary search to find lower_bound of X in interval [minElement,maxElement]. each time check the return value of lower_bound function whether it's distance from begin of multiset equals to N or not.
here is my code.
There is no a efficient way to reach nth element of the multiset. But in your problem we can do it like this :
I tried this code with several inputs and it worked. Even so sorry for if there is a bug. And notice that in each loop there have to be at least i elements in the multiset to reach ith element :)
I understood... But what will be ? If n is incremented by 1 after 1,2,3,.... insertion
how would I do fast access ?
It is easy too.
EDT
what's the complexity for this code
++ and -- operations on set iterators both have a complexity of O(logN) (N is the number of elements). The total complexity should be NlogN.
How did you end up reading this 5-year old post btw?
A tip for you since you're starting CP:
Don't ask about problems from ongoing contests.
+1