agrawaltanmay17's blog

help me to reduce time complexity
By agrawaltanmay17, history, 4 months ago, In English

I am using distance function in multiset but it requiers a time complexity of O(n) please help me to count the number of elements which are lesser or equal to a perticular element in multiset

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Can't do this in the STL multiset. But you can use the PBDS ordered set. See this blog.

To use the set as a multiset, you can make each element a pair. Something like, instead of inserting $$$a_i$$$ in the set, insert $$$(a_i, i)$$$.

→ Reply