Siraps's blog

Wrong answer on Codeforces EDU segment tree task. What is wrong with my code?
By Siraps, history, 4 years ago, In English

I am trying to solve E. Addition to Segment but for some reason I keep getting wrong answer on test case 3.You can see my code here. The weird thing is that when I change my set() function to the following:

void set(ll i, ll v, ll x, ll lx, ll rx)
	{
		if(i>=rx || i<lx) return;
		
		if(rx-lx==1)
		{
			values[x]+=v;
			return;
		}
		int m=(lx+rx)/2;
		set(i,v,2*x+1,lx,m);
		set(i,v,2*x+2,m,rx);
		values[x]=merge(values[2*x+1], values[2*x+2]);
		return;
	}

I get WA on testcase 63 (instead of testcase 3). This makes no sense to me because the two implementations of the set function should be logically equivalent. What is going on here?

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Added this at the begging of your set function and now its AC.

code

Its up to you to figure out why :)

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

    When the right border of the segment we want to change is n, the program will try to substract from the element with index n which is out of bounds. That line is to prevent this. Is this why?

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

      Lol, indeed. First of all I thought that's solves the problem because set sometimes go in wrong direction, but this theory was declined because there's is ifs in your code that already prevent it. So, I just wrote "Its up to you to figure out why :)" to make it looks like I know why it works. But yeah, you don't need this if statement actually, you can just make segtree of size n+1, instead of n, and it will fix the bug.

      → Reply