sudddddd's blog

By sudddddd, history, 7 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

| Write comment?
»
7 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.