×

# SPOJ - GSS1 - Can you answer these queries I

 1 http://www.spoj.com/problems/GSS1/ 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: https://codeextractor.wordpress.com/2016/07/11/playing-with-ranges-segment-tree/ 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: http://ideone.com/MqeiLa Thanks. asked 20 Dec '16, 06:14 70●1●6 accept rate: 14%

 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 && 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. answered 20 Dec '16, 07:51 4★anooakv 100●2 accept rate: 57%
 0 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 70●1●6 accept rate: 14%
 0 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 12●2 accept rate: 0%
 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 12●2 accept rate: 0% 1 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) Sorry, saw this late. Refer to what siddharth said :) (02 Feb '18, 22:59)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,755
×1,134
×75
×68
×21

question asked: 20 Dec '16, 06:14

question was seen: 3,316 times

last updated: 02 Feb '18, 22:59