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


SPOJ - GSS1 - Can you answer these queries I

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:


asked 20 Dec '16, 06:14

epsilonalpha's gravatar image

accept rate: 25%

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;
        return query(l,r,m+1,e,2*node+1);
    else if(r<=m)
        return query(l,r,s,m,2*node);
        Data lQuery = query(l,r,s,m,2*node);
        Data rQuery = query(l,r,m+1,e,2*node+1);
        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.


answered 20 Dec '16, 07:51

anooakv's gravatar image

accept rate: 57%

edited 20 Dec '16, 08:41

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.


answered 20 Dec '16, 18:13

epsilonalpha's gravatar image

accept rate: 25%

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)??


answered 01 Feb '18, 21:47

abhi007rider's gravatar image

accept rate: 0%

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



answered 01 Feb '18, 21:59

abhi007rider's gravatar image

accept rate: 0%

edited 01 Feb '18, 22:00


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.

(02 Feb '18, 22:52) siddharthp5384★

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

(02 Feb '18, 22:59) vijju123 ♦♦5★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 20 Dec '16, 06:14

question was seen: 3,378 times

last updated: 02 Feb '18, 22:59