Блог пользователя Matrix.code

Fast Access in Multiset

Автор Matrix.code, 12 лет назад, По-английски

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 ??

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
← Rev. 7  
Проголосовать: нравится -14 Проголосовать: не нравится

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.

→ Ответить
»
12 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

There is no a efficient way to reach nth element of the multiset. But in your problem we can do it like this :

    multiset<int> Set;
    multiset<int>::iterator ith; // iterator for ith element in multiset
    
    for(int i=1;i<=n;i++){
        cin >> k; // number of elements to insert in this loop
        
        while(k--){
            
            cin >> x; // element to insert
            Set.insert(x);
            
            if( Set.size()==1 ){    // first element inserted 
                ith = Set.begin();
            }
            else if( x <= (*ith) ){ 
                ith--;
            }
        
        }
        
        cout << *ith << endl; //ith element is here
        
        ith++;
    }

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 :)

→ Ответить