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

hide comments
skroxx: 2016-09-29 21:22:34

without range of M how can we compute the complexity for this problem?

srinath: 2016-09-20 10:11:46

Took me 13 submissions to get AC ;)

Eduard Rostomyan: 2016-09-19 16:16:57

Will the BIT work here?

stiffler22: 2016-09-06 23:47:00

using maximum sub array and getting WA on judge 9. Which case am I getting wrong?

rampant_lancer: 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
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?

rayhan50001: 2016-08-06 22:02:29

Last edit: 2016-08-06 22:10:14

Added by:Nguyen Dinh Tu
Date:2006-11-01
Time limit:0.115s-0.230s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS NODEJS PERL 6 VB.net