Блог пользователя sonjoydabnath

Автор sonjoydabnath, история, 9 лет назад, По-английски

Today I tried to solve Problem D(div2) of last Contest ( Codeforces Round 310 (Div. 2) ). In this problem I used lower_bound() function on a set of pair of pair and int ( set< pair< pair<long long, long long> , int > > ). Here is my ACed submission 11834954 and my TLE submission 11835029 . I don't know why I get TLE in second code. :S

Ok, Let me explain what I 've done here, I have a set like set< pair< pair<long long, long long> , int > > bridges on which I tried to apply lower_bound() function ( in line number 171 in my both code ). In first submission I used lower_bound() as like bridges.lower_bound(make_pair(keyValue,0LL)) and I got AC. But in my second code I used lower_bound() as like lower_bound(bridges.begin(),bridges.end(),make_pair(keyValue,0LL)) and I got TLE on case 11.

What is the difference between calling lower_bound() function in above mentioned 2 way ?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by sonjoydabnath (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Unfortunately, lower_bound(set.begin(), set.end(), x) works in O(N). Use set.lower_bound(x) to reach O(logN) complexity.

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    can you plz explain why it works in O(N) ? Is this O(N) complexity only applied for set ? I used lower_bound in this way with vector but got Aced in many problems?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Read about random-access iterators :) Briefly: in set you can only increment or decrement it, but in vector you are able to take (lo+hi)/2.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        what about this soln 11833491 ? here I used vector instead of set and got TLE...

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          I never told vector is better than set :) Of course, it depends on problem. I'm not sure, but I think in this code your trouble is in erase(). According to this it is linear in time. So, your algo works in O(n^2) in this case. By the way, erase(position) in set is amortized constant (link).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      As Totktonada said above, std::vector uses random access iterators, that allows you to access any element directly.

      Std::set uses bidirectional iterators, and you can only go forward or backward using it (you cannot access elements directly).