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 4 5 6 7 8 9 10 11 12 13 14 Next >

	gourab19964u: 2019-11-27 16:36:39 What is there in the 9th Test Case? For all -ve I have return -1e18 then to I am getting WA. I have checked with 5 -1 -1 -1 -2 -3 1 1 2 Ans: -1 then what's going wrong in my solution. I have used a segment tree as it will have O(max(mlogn,nlogn)) / time complexity complexity Last edit: 2019-11-27 19:27:29
	fardin_abir: 2019-11-04 08:57:03 Solved it using segment tree, main challenge is merging two node... and avoid returning zero from unnecessary nodes, it causes WA in test case 9.
	gabadzeluka: 2019-10-28 14:46:53 Solved it!!! if u have wrong answer on 9th test case try this (all negative): 5 -1 -1 -1 -2 -3 1 1 2 answer is -1
	manuver: 2019-10-15 08:06:39 for WA on 9 Test case: do not return 0 if all values in given range are -ve return the smallest neg val, caused me 3 WA AC in 0.36 seconds using segment tree in C++
	wingman__7: 2019-10-10 08:51:38 I went through all the comments, everyone is talking about Kadane's algo but time complexity of Kadane's algo is O(n) and if we answer "m" queries total time complexity will become O(mn). The problem setter has fixed the time limit and value of "m" such that the 9th test case will fail. You have to implement segment tree, then the total time complexity will be O(mlogn).
	mriow: 2019-09-25 12:26:57 For some reason i got 1.42 seconds but the submission was accepted...
	rahulsinghk: 2019-09-17 18:57:31 what is 9th test case??
	ajv123: 2019-09-12 17:36:59 Does someone know what the 9th test case is?
	nprakhar: 2019-08-21 13:20:23 Even after using Kadane's Algorithm with fast I/O I'm geeting TLE on test 9....
	nprakhar: 2019-08-21 12:57:22 I used Divide and Conquer Approach for this problem so Time Complexity is O(mnlogn). I'm getting TLE in test 9. Any better approach?

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