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
heartless_2811: 2020-03-23 14:31:49

help me debugging this code !! I think it's failing on test case 9 https://ideone.com/5Efoaw

shanto09: 2020-03-23 08:43:26

A problem worth solving!

vritta: 2020-03-22 11:14:34

For the newbies you can see explanation on my blog(read the comments for explanation), copy the code on your IDE & remove unnecessary comments it will become short- "https://spojsolutionsgss1.blogspot.com/2020/03/pre.html"

herrdirektor: 2020-03-17 17:00:18

solved after many attempts. Total satisfaction after solving this one

omega1100100: 2020-03-15 05:27:23

I solved it with Java & Segment Tree after 7 attempts.

Last edit: 2020-03-15 05:27:50
sharjeel_spoj: 2020-03-10 20:05:23

1 based indexing has been used for query range inputs.

priyansh19077: 2020-03-02 18:01:16

Getting a wrong answer on test case 9. Does anybody know where I could be going wrong

priyansh19077: 2020-03-02 17:58:55

We need to find the maximum value in the range given as a query right. Does that plus sign between the elements of the array signify anything or it's just there without any reason?

jorge_iba: 2020-03-01 21:07:06

For WA in test case 9 try to check if you Merge function it's okay at the moment of answering the queries, it's not the same Merge( Ans, Current) and Merge(Current, Ans).

mrmajumder: 2020-02-02 18:09:55

Learned segmented tree to solve this.
Learned the iterative approach.
You may learn this too, segmented tree is the answer for most range related tasks.


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