SPOJ - GSS1 - Can you answer these queries I

general
, , , ,
1

Since this problem is set for segment trees, Kadane’s algorithm failed. So I looked up segment trees and got the gist of it. I followed this for learning the basics:

After trying few times, I got my code working, but got a WA for final test caes, so I googled up the concept of maximum subarray and managed to get it working, but now my implementation times out, even with optimized IO (beyond scanf and printf, using one of those fancy templates available online)

I decided to remove everything, including vectors, and deal purely with arrays and scanf/printfs and I still get a time out. Either the time limit is really strict or the code doesn’t work as I think it should and maybe gets stuck.

Here is my final implementation using arrays:

Thanks.

1 Like
2

You have done a mistake in your code ,

in line no. 55 ,
in Data query(int l, int r, int s, int e, int node) function.

here it is,

make the above function as follows:

Data query(int l, int r, int s, int e, int node)
{
	Data d;
	if(s>r || e<l)
		return d;
	else if(s>=l && e<=r)  //use this instead of '(s>=e && e<=r)'
		return tree[node];

	int m = s+(e-s)/2;
	if(l>m)
		return query(l,r,m+1,e,2*node+1);
	else if(r<=m)
		return query(l,r,s,m,2*node);
	else
	{
		Data lQuery = query(l,r,s,m,2*node);
		Data rQuery = query(l,r,m+1,e,2*node+1);
		calc(node,d,lQuery,rQuery);
		return d;
	}
}

The AC solution of your code is here.

Here you have to check whether the current node is completely inside the range or not.

If it is completely inside the range, then return the node.

I have solved the same problem, you can see my solution on github.

Hope this is helpful. If you still don’t get anything ,feel free to ask.

1 Like
3

What a silly typo, I didn’t even notice it… and here I was trying to optimize IO.
Thank you so much, I’ll take much better care next time.

4

can you please explain what actually we have to do i am not able to undesrtand?? stuck between max and all (what is the need)??

5

can u plz tell me the approach in this question i m not able to understand what actuall quest wants!!
@vijju123

linl-> http://www.spoj.com/problems/GSS1/

6

Question asks for maximum sub range sum, just like you calculate maximum sub array sum (u can consider this as range from 0 to n-1). Here you have to answer maximum sum in range l to r.
here you can get a nice explanation.

1 Like
7

Sorry, saw this late. Refer to what siddharth said :slight_smile: