Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

agrawaltanmay17's blog

help me to reduce time complexity
By agrawaltanmay17, history, 2 years 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

»
2 years ago, hide # |
← 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