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


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-RHINO NODEJS PERL6 VB.NET