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
Joyjit Choudhury: 2017-05-25 05:03:27

After fixing all probable bugs in my code, I was still getting TLE on Test Case 9.
Changed cin, cout to printf, scanf and removed ios::sync_with_stdio(false) and AC :)

swas99: 2017-05-20 08:13:45

Failed to do it in java. Wasted my time even trying to optimize the input scan. Just reading the input using Scanner or Buffered reader give TLE. Due to source code limit, I could not try other options.
Please let me know if anyone got AC using java

shamiul93: 2017-04-21 00:23:26

Getting RTE in test case 9. :( Anybody help please.

anurag_333: 2017-04-08 14:42:13

10
-200 3 4 -200 6 2 4 -200 5 6
1
1 10
op should be 12

anurag_333: 2017-04-08 14:21:59

@ayush_1997 check test case of @marshmellow;
dont return 0 in querrys base case
return -15008//check least value of |ai|in ques

ayush_1997: 2017-04-01 07:48:57

wa on test case 9:(
tried everything..

rohit9934: 2017-03-30 15:35:11

Ohhhaaa This one is tough man,Specially for me who dont know how the f we can store 3,4 values simultaneously in a node.Took me 4-5 days understanding and solving.Can This problem be solved using BITs?

ace_of_spades: 2017-03-19 10:22:24

Last edit: 2017-03-19 21:38:09
marshmellow: 2017-03-19 09:55:24

input:
3
-1 -2 -3
1
1 3
output:
-1

scorpion_ajay: 2017-03-19 07:54:59

@anurag_333
No, i tried solving it using kadane but it gave me tle for obvious reasons that it can be O(n) in worst case !!
Also you have to check every time you query so it exceeds the time limit and ultimately you are better with seg_trees..


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