Hello, Codeforces!
I want to ask if somebody can help and explain why something like this can happen.
Basically I was implementing a segment tree using push down technique to imple adding a number on a segment in 739C - Alyona and towers. After writing it correctly I've got stuck on test 4. I've gone through a huge stress test (about 20000 tests) and did not spot the mistake.
After two hours more I've added #define int long long
in the beginning of the program. It helped me to pass test 4, but it got TLE on test 47. As you can probably tell I couldn't have told why did it help. And since I write this entry I can't tell now. After a little investigation I found out that the only difference is in a small method void add(int d)
. Here are the codes: Wrong Answer 4 and Accepted. The only thing changed is void add(int d)
is now void add(long long d)
. Inside of the function the only thing i do is
void add(int d) {
p += d;
left += d;
right += d;
}
All variables p
, left
and right
are long long so the only difference is in d
. This difference means that long long += int
does not work as (I) expected. I've always thought it converts int
to long long
and then sums up. Seems it is not the case.
I was wondering whether somebody can help me and give explanation. Also would like to read how do you manage such problems like overflow on contests.
Thanks in advance
UPD: Problem solved.
Difference is when you are trying to call add with parameter that doesn't fit in int. You have such calls in your code, check push method.
Oh god, thank you so much, I've spent too much time on it.