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 22 23 24 25 26 27 28 29 30 31 32 Next >

	top_gun007: 2016-09-03 10:51:45 took me a day... follow the link http://wcipeg.com/wiki/Segment_tree
	testing java: 2016-08-23 18:58:00 The time limit is absurd. Still don't know whether I have some coding errors or my java is simply too slow to make it through. edit: like really absurd, same code which gave me AC now gets TLE Last edit: 2016-08-24 11:38:29
	davidgalehouse: 2016-08-23 08:26:22 Note to C# solvers: This is a really good problem to learn segment trees (don't use wikipedia as a reference, I recommend http://wcipeg.com/wiki/Segment_tree). Unfortunately, there are some annoying little issues. Use StringSplitOptions.RemoveEmptyEntries (or maybe just Trim?) to avoid runtime error. Use string builder and a single Console.Write(). And just in case, beware a bug in the Mono compiler about invalid IL code generation (I got this when doing multiple assignment inside of a constructor, like PropA = PropB = value). Last edit: 2016-09-25 20:57:40
	xunx: 2016-08-09 11:41:47 getting TLE which data structure shall I use?
	giriprasad kemburu: 2016-07-29 21:50:07 Using bufferedreader causes NZEC.Can anyone tell me how to fix this problem.It works fine on my ide and some other problems also works fine with scanner but not with bufferedreader.
	Mohamed Elnaggar: 2016-07-25 12:56:49 I cant Expect What is The Wrong ? Getting WA and I used (Segment Tree) Data STructures any Help !!
	flyingduchman_: 2016-07-21 14:16:15 Took almost one month to get accepted
	naksh9619: 2016-07-19 02:00:07 good problem :) Last edit: 2016-07-19 22:32:40
	baadshah_: 2016-06-26 14:15:48 Finally AC took whole DAY!!
	Deepak : 2016-06-18 17:27:55 finally AC..great problem for beginners.thanks @AbhishekRajput

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