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
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 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).

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
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


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