Jame___boy's blog

By Jame___boy, 5 months ago, In English


For random access iterators, std::distance is O(1). Unfortunately set iterator does not support random access, so the std::distance algorithm has to iterate over the pointers to compute distance, and worst case is O(n).
Example: https://codeforces.com/contest/1915/submission/239386119 (Time limit exceeded)

You can achieve O(log(n)) distance complexity in sets if you use Policy Based Data Structures(PBDS).
Example: https://codeforces.com/contest/1915/submission/239436173 (Accepted)


For std::vector the complexity is O(1) since the iterators support random access. You can also use subtraction operator with the same effect.
Example : (int) (lower_bound(vec.begin(),vec.end(),x) — v.begin()) returns distance from begin to first element in array with value >= x, so it's the same as std::distance(vec.begin(), lower_bound(vec.begin(),vec.end(),x));

Some useful links:

  1. https://youtu.be/MiBrJTNOEP0?si=12Op-IbK7lfqdIbp (বাংলা ভিডিও টিউটোরিয়াল)
  2. https://codeforces.com/blog/entry/45902 (Time complexity of std::distance)
  3. https://stackoverflow.com/questions/13505562/getting-index-of-set-element-via-iterator/13505578
  4. https://codeforces.com/blog/entry/5631?#comment-239276 (How to access to i*th element of a set in c++ effectively (*O(1) or (logN))?)
  5. https://codeforces.com/blog/entry/11080 (C++ STL: Policy based data structures)
  6. https://codeforces.com/blog/entry/11080?#comment-533322 (drawback of using less_equal)

PBDS Code:

  1. https://codeforces.com/contest/1915/submission/239310664
  2. https://codeforces.com/contest/1915/submission/239442547
  • Vote: I like it
  • -8
  • Vote: I do not like it

5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Thanks for share this useful resources. I solved last contests F using brute force that's why it take 4.5s :( I will try this PBDS next time

5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I think it is O(logn) in the second case... Correct me if I am wrong...

4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is what exactly happened to me in 918 Div. 4 as you showed here. I could not fix at the time but I guess it is very helpful for beginners to know this concept.