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?
lower_boundreturns an iterator. So you're basically adding a number to an iterator and then subtracting an iterator. Ifspin*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.
Well, stackoverflow tells me it should be fine as long as not dereferencing
spin*n + lower_bound(). I am confused.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.