SPOJ.com - Problem GSS1

GSS1 - Can you answer these queries I

#tree

You are given a sequence A[1], A[2] ... A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x, y) = Max { a[i] + a[i+1] + ... + a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.

Input

The first line of the input file contains the integer N.
In the second line, N numbers follow.
The third line contains the integer M.
M lines follow, where line i contains 2 numbers xi and yi.

Output

Your program should output the results of the M queries, one query per line.

Example

Input:
3 
-1 2 3
1
1 2

Output:
2

Submit solution!

hide comments

< Previous 11 12 13 14 15 16 17 18 19 20 21 Next >

	codehead1997: 2018-08-02 15:41:47 If you are getting TLE at testcase #9 instead of copy pasting the code submit your code file.You will thank me later.
	DOT: 2018-08-01 19:06:04 1. To people getting WA for #9, ensure while computing the best in a range, you also check the elements individually. I missed that. 2. long long is not needed. int is enough for handling this condition (\|A[i]\| ≤ 15007 , 1 ≤ N ≤ 50000). Max value you can make is 15007 * 50000, well within the int range. 3. First seven cases are very weak. I misunderstood the question completely and was printing the max element in [l, r] and got WA only at #8. :P 4. Segment tree seems to be much faster than square root decomposition for this question Last edit: 2018-08-01 19:07:53
	jason_chatz: 2018-07-24 14:38:13 Generally the suggestions in the comments are very good. One thing i would like to add is that even though most sites state that the segment tree array should be 2N that is only true when N is a power of two, supposing a simple implementation of segment tree. Therefore a good size is 4N. BTW a good testcase i found on SPOJtoolkit is the following : 9 324 3 23 -234 32 -4 324 435 -5775 3 1 4 3 5 5 9
	kiquance21: 2018-07-03 04:42:13 How to check ,in which test_case it's failing,I see everyone posting fails on TC 9,When I click on my submission it only shows WA
	na0013: 2018-06-22 10:22:02 Looks like something wrong with the judge.. First try-- TLE on (9) --<no edit> second try--TLE on(7) --<no edit> third try --TLE on (9) --<no edit> fourth try-- whoa! AC this time !! Didn't understand what happened!
	ankur314: 2018-06-21 07:05:46 THOSE WHO HAVE PROBLEM WITH TESTCASE 9: I made a mistake in my code by considering that maxsum could be found only in prefix or suffix. It gave correct answer till TC8 . But TC 9 probably has a solution where max sum is contained in subarray. Check this case: Input: 6 -200 143 23 -231 123 33 1 1 6 correct output:166 But if you are not combining nodes properly, output:156(WRONG)...
	excel_blaze: 2018-06-13 20:08:48 feels good!! nice one scanf printf will work
	kr_4shivam: 2018-06-13 19:26:07 i am getting WA on TC 9 any hint will be very helpful.Thanks
	maddythakker: 2018-06-10 11:49:42 FOR THE ONES GETTING TLE/WA ON JUDGE - 9 : 1) RETURN - MAX_INT IN CASE OF NO OVERLAP 2) USE FAST I/O 3) USE LONG LONG
	shizukaa: 2018-06-09 09:38:15 @thanos_tapras Thanks bro, reading comments helps ;) #was struck with the same problem

Submit solution!

Added by:	Nguyen Dinh Tu
Date:	2006-11-01
Time limit:	1s
Source limit:	5000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO NODEJS PERL6 VB.NET