okwedook's blog

By okwedook, 5 years ago, In English

Hello, Codeforces!

I want to ask if somebody can help and explain why something like this can happen.

The story behind this

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.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Oh god, thank you so much, I've spent too much time on it.