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
coder_100: 2020-07-28 11:26:06

why I am getting WA even after changing Integer.MIN_VALUE to -15008

rahul7777: 2020-07-23 04:01:16

how to check test cases

jrseinc: 2020-07-16 19:10:45

can someone explain to me why returning INT_MIN gave WA while using -15008 gave AC? For the 9th testcase.

mehulcoder: 2020-07-07 21:12:38

Try to read about segment trees from here, this is THE best source on the internet:
https://cp-algorithms.com/data_structures/segment_tree.html

ambuj2512: 2020-06-30 16:06:27

If you are getting wrong answer even after getting AC on all your custom input then change the value of most negative to -1e9 if you take -1e18 then it can overflow and if you take less then -1e9 then it will change the answer

Last edit: 2020-06-30 16:07:09
worrywart_ind: 2020-06-12 07:26:14

@yourmom_ thanks dude

ronythakur: 2020-06-02 20:38:32

change '\n' to endl if you still getting wa

saurabh32gupta: 2020-05-29 20:37:53

if anyone facing TLE in java even after using segment tree then try 4th input method from here : https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

Last edit: 2020-05-29 20:38:26
avikram553: 2020-05-26 12:40:47

Does anyone got AC in Python?
My code works fine on every testcase given in the comment section but it gives TLE on testcase 9.
I have used segment tree with a node contaqining 4 values i.e
bestleft bestright totalsum maxsum.
Still i am getting TLE ,Anyone know whyy??

Last edit: 2020-05-26 12:43:59
balbeer3099: 2020-05-26 07:49:09

@jabhi_18 Your test case output is fine on my code, My submission runs fine till 8th but gives W/A on 9th.
@fighter_4 I've kept the size of tree 4*n ... still it's W/A on 9th


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