### Night_L's blog

By Night_L, history, 6 weeks ago,

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?

• +5

 » 6 weeks ago, # |   +6 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 →   0 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, # ^ |   0 Well, stackoverflow tells me it should be fine as long as not dereferencing spin*n + lower_bound(). I am confused.
•  » » » 6 weeks ago, # ^ |   0 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.