ShaFeiii's blog

Unexpected Time Limit !!
By ShaFeiii, history, 3 weeks ago, In English

When I tried to upsolve this problem 706B - Interesting drink I faced an undefined time limit!!

In my first approach, I solved it using a multiset and upperbound 294508423 I got time limit on test 11

then, tried to solve with vector and sorting, which got accepted 294508512

Can anyone help me understand what the issue was?

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

»
3 weeks ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

auto price = prices.upper_bound(x); int canBuy = distance(prices.begin(), price);

The calculation of canBuy takes $$$O(n)$$$ time in the worst case instead of $$$O(\log n)$$$ as you suppose, where n = prices.size(), since the time complexity of distance(prices.begin(), price) is $$$O(n)$$$ in the worst case, because these iterators are not random access.

Time complexity of std::distance( InputIt first, InputIt last ) is constant only if InputIt is the random access iterator, else it is linear.

→ Reply