Night_L's blog

By Night_L, history, 6 weeks ago, In English

In this 109101215, I got WrongAnswer because of an overflow. The overflow comes from

long long a[N], x[N], ans, spin;
int n;
vector<long long> sum;
...
ans = spin*n + lower_bound(sum.begin(),sum.end(),x[i] - spin*a[n-1]) - sum.begin();

I manage to fix it by adding parenthesis to lower_bound(..)-sum.begin().

This is learned from other guys' code. But I have no idea what I am doing and what has been corrected. Can someone explain what happens?

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

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

lower_bound returns an iterator. So you're basically adding a number to an iterator and then subtracting an iterator. If spin*n + lower_bound(...) points outside the array, the behavior is undefined. That's exactly what happens here.

When you add parentheses, you first subtract iterators and then add two integers together. There is no UB here.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks a lot. Someone tells me the value comes from int or long long overflow. But I doubt that. So the behavior comes from an out-of-bound iterator usage due to the calculation order, right?

    CodeForces diagnosis does not have that detection currently, so it does not give a hint of "integer overflow". This makes sense.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, stackoverflow tells me it should be fine as long as not dereferencing spin*n + lower_bound(). I am confused.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm not sure where you found that claim. The standard as well as answers to two StackOverflow posts: link 1, link 2 both claim it's UB.