code_fille's blog

Can somebody figure out the bug in the binary search used in the code!
By code_fille, history, 9 years ago, In English

622C - Not Equal on a Segment 15943480 It gives TLE on test case number 14!

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A long code without any explanation. Don't be surprised that you don't get help.

EDIT — The next paragraph is bullshit, don't read it.

I have read your code and I think its complexity is O(n·m) because of line:
p=lower_bound(h[x].begin(),h[x].end(),l);
Note that lower_bound() is linear for vectors. Write your own binary search there.

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

    http://www.cplusplus.com/reference/algorithm/lower_bound/

    Lower bound is O(LogN) for random access containers is what is mentioned here..Is lower_bound really linear for vectors?

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

    Of course it is logarithmic for vectors as they are random-access containers. Did you mean anything else?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lower_bound(x.begin(),x.end(),a) -> x.lower_bound(a)

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

      That syntax is only true in case the container has lower_bound as a member function. So it's valid for something like sets, but not valid for vectors.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No its not linear. The same got AC with fast I/O and using iterative binary search.

    → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Replace endl with "\n".

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And pass vectors by reference in functions flr() and sr().

    → Reply