rick_sanchez_c-137's blog

Same ideia from the editorial gets TLE (very clear code)
By rick_sanchez_c-137, history, 8 years ago, In English

UPDATE: The problem was found. It was that I should not have used the the generic lower_bound function from algorithm library (I should have used the specific lower_bound from the STL multiset)

Hello!

Regarding this problem, my code (not avaible anymore) implements the same ideia from the following editorial and gets TLE.

Do you know what part of my code is too slow? In my point of view, the code is exacly equal the editorial.

Thanks a lot!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Generalized lower bound doesn't work well on tree data structures.

Use mp.lower_bound(value) and you'll probably get ac :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    OMG! Thanks a lot! I wish I could give you multiple upvotes. I will friend you, that's what I can do to show my apreciation I guess :)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    You're right. I didn't realize that until playing with them on my own.

    std::lower_bound (or similar functions) will produce the correct answer, but for non-random-access iterators (e.g., trees like for sets or maps), the running time will be linear, rather than logarithmic. Some reference: http://www.cplusplus.com/reference/algorithm/lower_bound/

    BTW, when I first solved this problem a few years ago, I didn't think about maintaining the pareto front explicitly, though there is the first sorting part. Instead, I just used a MIN Fenwick tree with r2 as the index and r3 as the value.

    → Reply