sudddddd's blog

By sudddddd, history, 3 years ago, In English

Hello, this is my first problem on segment tree. I have used segment tree to solve this problem but I am getting Wrong Answer on a test case. Can you point out what is wrong. Thank you

Problem Statement

My Code

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Your query function was not correct as it was not returning required answer when the search was out of range as the new node with values -15000 was made and querying using it was creating a problem. Also it modified the tree sometimes. Here is how you should query on the segment tree :

list* query(list* tree[],int node,int low,int high,int l,int r)
{
    if(low==l && high==r)
        return tree[node];
    int p1 = 2*node+1, p2 = 2*node+2, mid = (low+high)/2;
    if(r<=mid) 
    	return query(tree,p1,low,mid,l,r);
 	if(l>mid)
 		return query(tree,p2,mid+1,high,l,r);
    list *a=query(tree,2*node+1,low,(high+low)/2,l,mid);
    list *b=query(tree,2*node+2,(high+low)/2+1,high,mid+1,r);
 	list *n;
    long w=a->sum+b->sum;
    long x=max(max(a->bestsum,b->bestsum),a->right+b->left);
    long y=max(a->left,a->sum+b->left);
    long z=max(a->right+b->sum,b->right);
    n=make_new_node(w,x,y,z);
 
    return n;
}

I replaced your query function with the above function and got AC. Here is the link to the AC code.

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

    Thank You very much

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

    Can you please give me a test case where my code is wrong? (I understood that I should not have updated the tree in query function)