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 1 2 3 4 5 6 7 8 9 10 11 Next >

	kushal_0189: 2020-09-02 16:22:16 Use Concept of Prefix and Suffix sum of an array Last edit: 2020-09-02 16:22:39
	coder_100: 2020-07-28 11:26:06 why I am getting WA even after changing Integer.MIN_VALUE to -15008
	rahul7777: 2020-07-23 04:01:16 how to check test cases
	jrseinc: 2020-07-16 19:10:45 can someone explain to me why returning INT_MIN gave WA while using -15008 gave AC? For the 9th testcase.
	mehulcoder: 2020-07-07 21:12:38 Try to read about segment trees from here, this is THE best source on the internet: https://cp-algorithms.com/data_structures/segment_tree.html
	ambuj2512: 2020-06-30 16:06:27 If you are getting wrong answer even after getting AC on all your custom input then change the value of most negative to -1e9 if you take -1e18 then it can overflow and if you take less then -1e9 then it will change the answer Last edit: 2020-06-30 16:07:09
	worrywart_ind: 2020-06-12 07:26:14 @yourmom_ thanks dude
	ronythakur: 2020-06-02 20:38:32 change '\n' to endl if you still getting wa
	saurabh32gupta: 2020-05-29 20:37:53 if anyone facing TLE in java even after using segment tree then try 4th input method from here : https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ Last edit: 2020-05-29 20:38:26
	avikram553: 2020-05-26 12:40:47 Does anyone got AC in Python? My code works fine on every testcase given in the comment section but it gives TLE on testcase 9. I have used segment tree with a node contaqining 4 values i.e bestleft bestright totalsum maxsum. Still i am getting TLE ,Anyone know whyy?? Last edit: 2020-05-26 12:43:59

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