Seg trees GSS1 SPOJ Runtime error

general
, ,
1

Problem link: https://www.spoj.com/problems/GSS1/

My code: https://hastebin.com/azuwerofin.cpp

This gives a run time error. Could anyone help me figure out what is wrong, or at least give me pointers on how to debug? This is one of my first segment trees questions.

Edit: On modifying the way I take input of no. of queries q, it is giving run time error at test case 9 or so.

2

You are taking, the number of queries input, right after n.

However, the question mentions the number of queries will be given after the array elements.

Edit:

I think you have wrongly implemented your query function.

When start and end are exactly in your range i.e(l==start and r==end) you are returning maxisum[node].

And in the last conditions where you are searching your range partially in left and right childs,
i.e where you are setting p1 and p2, your are using p1 and p2(which are values of maxisum for that recursive query) to access your sum,maxlsum,etc.

So, that will be causing array index out of bounds since you are indexing sum,maxlsum arrays with value of maxisum.

The solution to this is to return node in query function.
You can have a look at my solution

2 Likes
3

Hi. Here is your code. It doesnt give RE but is giving TLE. Also I dont think this is the question you should start with if you are implementing segment tree for the first time. Try this and this and few other easier problems on segment trees before attempting GSS1. :slight_smile:

1 Like
4

Thanks a lot for taking the time to modify the code and make it correct. I didn’t understand what was wrong in what I had done in my query function though. Could you explain why it is wrong?

5

Thank you so much! That was stupid of me.

6

It shouldn’t be that hard if you know what to store in nodes and how to merge two nodes correctly. If you provide me your code then I’ll figure out why it is giving wrong answer. I’m not very used to implementing segment tree in recursive way. But you can have a look to my solution.

[details=Click to view]

#include 
using namespace std;
struct Node{
	int MS,SS,PS,S;
        // ms- maxsum
        // ps- maxprefixsum
        // ss- maxsuffixsum
        // s- totalsum
	Node(){
		MS=SS=PS=S=0;
	}
};
Node combine(Node& a, Node& b){
	Node tmp;
	tmp.S = a.S + b.S;
	tmp.SS =max(b.SS,b.S+a.SS); 
	tmp.PS =max(a.PS,a.S+b.PS);
	tmp.MS =max(tmp.PS,max(tmp.SS,max(a.MS,max(b.MS,a.SS+b.PS))));
	return tmp;
}
Node iniLeaf(int x){
	Node tmp;
	tmp.S = tmp.SS = tmp.PS = tmp.MS = x;
	return tmp;
}
const int N = 1e5;
Node t[2*N];
int n;
void build(){
	for(int i=n-1;i>0;i--){
		t[i] = combine(t[i<<1], t[i<<1|1]);
	}
}
int query(int l, int r){
	Node resR,resL;
	bool b1,b2;
	b1 = false;
	b2 = false;
	for(l+=n,r+=n;l>=1,r>>=1){
		if(l&1){
			if(b1==false){
				resL = t[l++];
				b1 = true;
			}else{
				resL = combine(resL,t[l++]);
			}
		}
		if(r&1){
			if(b2==false){
				resR = t[--r];
				b2 = true;
			}else{
				resR = combine(t[--r],resR);
			}
		}
	}
	if(b1 && b2){
	    return combine(resL,resR).MS;
	}
	if(b1){
		return resL.MS;
	}
	if(b2){
		return resR.MS;
	}
	
	assert(false);
	return 0;
}
int main(){
	cin>>n;
	int tmp;
	for(int i=0;i>tmp;
		t[i+n] = iniLeaf(tmp);
	}
	build();
	int q;
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		cout<<  query(x-1,y) << endl;
	}
	return 0;
}