**set**

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://mirror.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://mirror.codeforces.com/contest/1915/submission/239436173 (Accepted)

**vector**

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

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

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

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

Thanks, For Your Attention. I have updated 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.