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

	oalieno: 2016-05-11 15:43:27 Did anyone use Treap to solve this problem? I keep getting TLE using Treap...(sad...)
	mars_ch: 2016-05-02 08:34:46 同意楼上！！
	yousiki: 2016-05-01 05:38:06 TL is too strict
	geekyadity: 2016-04-14 15:04:18 Use printf, scanf. ( sync_with_stdio(false) ) gives TLE with the same code
	a_b_c12345: 2016-04-10 09:16:53 yoo..!! after 2 WA and 2 TLE finally accepted. To get AC from TLE just changed input array and tree into global.
	minhthai: 2016-02-14 14:50:58 why hate java so much :(( for once, please increase the time limit for java
	Tomasz Plaskota: 2016-02-12 13:51:16 as mentioned before: make sure you use fast input output cause there is ALOT of that. Also to earlier questions: maximum of subarray algorithm works in general but you will still find it too slow for amount of queries M that test cases provide (even fastest MSA is O(NM), while ST will be O(N1))
	sanket407: 2016-02-05 14:27:47 FOR JAVA GUYS : USE fast input reader for ip USe stringbiulder to store op and print all at once at the end And maybe some optimizations inside
	nib: 2016-01-25 10:38:20 Extremely strict TL. Same idea using struct passed, but using vector gets TLE :/
	proficient: 2016-01-18 17:09:32 The problem requires fast input/output, I had a TLE even with sync_with_stdio(false) and tie(0)

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