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

lovish_0812: 2020-01-30 05:10:13

I think there is problem with test cases in this question. Is someone able to solve this question recently?

roopammishra: 2020-01-02 21:32:48

Test cases are weak!! My wrong solution got accepted.

dr_humble42: 2019-12-30 23:23:31

I'm getting a WA on test case number 9

thakkar2804: 2019-12-17 12:07:51

use -1e14 instead of -1e18

shoot_the_code: 2019-12-09 14:41:54

@gourab199964u Do not take -1e18 as it will overflow .Take -1e14 instead

Last edit: 2019-12-09 14:42:35
gourab19964u: 2019-11-27 16:36:39

What is there in the 9th Test Case? For all -ve I have return -1e18 then to I am getting WA. I have checked with
5
-1 -1 -1 -2 -3
1
1 2
Ans: -1
then what's going wrong in my solution. I have used a segment tree as it will have O(max(mlogn,nlogn)) / time complexity complexity

Last edit: 2019-11-27 19:27:29

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