Night_L's blog

What happens to this overflow?
By Night_L, history, 3 years 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

Comments Comments (3)
| Write comment?
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply