numbertheorist17's blog

Why does this happen?
By numbertheorist17, history, 9 years ago, In English

I was trying 484E - Sign on Fence. Here are my two submissions:

15442167

15442182

The only thing I changed in these two submissions is in the update method. Instead of having

int k = update(L[ID], low, mid, qx);
L[ID] = k;

I put

L[ID] = update(L[ID], low, mid, qx);

and the same thing with the array R. This should work the same way, but one gives Accepted and the other gives WA. Is there any specific reason why this happens?

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably I can explain that. When you write L[ID] = update(L[ID], low, mid, qx), you make a call into update(L[ID]) and after it finished work you go up into recursion. So in one step you change you L[ID], but at first(when you go down) that L[ID](from which you called this function first time) was different from current. And when you write K, you do not change L[ID] exact in function call, you do it after, so you will not have problems with changing argument you operate in recursion call.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it's because the value ID changes after you summon the update function

L[ID]=k has a different ID than the line above it

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

When you write f()=g() order on which functions are evaluated is not specified. In your case, left hand side of evaluated, returning reference, then in recursion you resize the vector causing reallocation, making reference no more valid. Then you write to invalidated reference which is UB.

reserving vector in advance would help

→ Reply