You are not logged in. Please login at www.codechef.com to post your questions!

×

Seg trees GSS1 SPOJ Runtime error

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.

asked 19 Jun '18, 11:47

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%

edited 20 Jun '18, 10:33


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

link

answered 19 Jun '18, 12:29

adzo261's gravatar image

4★adzo261
2898
accept rate: 37%

edited 20 Jun '18, 12:26

Thank you so much! That was stupid of me.

(19 Jun '18, 14:50) sandy9992★

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. :)

link

answered 19 Jun '18, 12:38

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

edited 19 Jun '18, 12:41

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?

(19 Jun '18, 14:49) sandy9992★

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.

View Content
link

answered 20 Jun '18, 15:52

meet2mky's gravatar image

4★meet2mky
2013
accept rate: 26%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,768
×1,137
×21

question asked: 19 Jun '18, 11:47

question was seen: 214 times

last updated: 20 Jun '18, 15:52