Runtime difference of using std::upper_bound on different underlying data structures?

Правка en1, от the_stone_dawg, 2022-02-05 04:40:54

Hi there, while working on this problem, I ran into a situation where using std::upper_bound(set) TLE'd, while replacing the set with a sorted array was comfortably within the time constraints. (TLE submission: 145179964, AC: 145179970). AFAIK, these two should be equivalent O(log n), up to constants. In practice, is it just that those constant factors are great enough to TLE solutions that are asymptotically within the constraint, or is there something else I'm missing when using std::upper_bound with sets instead of vectors?

Thanks!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский the_stone_dawg 2022-02-05 04:40:54 807 Initial revision (published)