GSS1 - Can you answer these queries I

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

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

hide comments
2016-10-07 12:35:30
used kadane algo for worst case scenario complexity is O(n*M), but TLE is the verdict !
how to improve this approach ? and also what is the limit of M ?

Last edit: 2016-10-07 13:23:13
2016-10-05 13:11:29 Anirban Acharya
test cases are pretty weak.. I got 3 of my solutions passed by introducing several bugs :p .. so guys, even if your solution passes the test cases, make sure your algorithm and/or implementation is actually correct.
2016-10-03 12:00:52 rahul
Source limit is 5kB?!
Weirdest thing ever
2016-10-02 06:51:19 herkeyrefugee
Except for fast I/O don't look for anything , u can solve it .... :)
2016-09-29 21:22:34
without range of M how can we compute the complexity for this problem?
2016-09-20 10:11:46 srinath
Took me 13 submissions to get AC ;)
2016-09-19 16:16:57 Eduard Rostomyan
Will the BIT work here?
2016-09-06 23:47:00
using maximum sub array and getting WA on judge 9. Which case am I getting wrong?
2016-09-06 18:23:35
getting sigsegv can someone point out some common mistakes.I am using segment tree.

Last edit: 2016-09-06 18:23:56
2016-09-03 10:51:45
took me a day... follow the link http://wcipeg.com/wiki/Segment_tree
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.