SPOJ.com - Problem GSS1

GSS1 - Can you answer these queries I

#tree

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	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
	viper_1: 2020-05-23 13:50:17 for initialization of node values use numeric_limits<short int>::min()
	varunsainii: 2020-05-20 07:47:59 If you are learning from cp-algorithms, then make sure that you notice the change. According to cp-algorithms if all numbers are negative then you must print 0, on the other hand here you have to print the greatest -ve number in that case.
	jabhi_18: 2020-05-18 21:52:38 testcases from 1 to 8 are of no use.You can even print the minimum in the range and it will be passed upto test case 8.. one can try this: 10 3 4 5 -4 5 -5 -5 8 3 -3 5 1 4 3 5 5 8 10 10 1 10 output: 12 6 8 -3 14
	kamina01: 2020-05-11 11:51:30 my first segment tree question...ac in one go...
	yourmom__: 2020-04-26 08:22:55 (For java bois) For people who are getting TLE even after using Segment tree, try one of these methods: 1. When you have got the result of a query, don't just print it to the console on the fly. While printing, the program pauses, which lengthens the time for execution. Instead what you can do is, make a StringBuilder object, and append to it the intermediate answers (by adding "\n", to all but the last one). After you are done, just print out the String. This worked for me. The execution time using this was around 5.8 seconds (and yes I used plain old Scanner, no modifications) and was accepted. 2. If even after this you are getting TLE, refer this link for fast I/O in java: https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ The execution time using this was around 2.3 seconds Last edit: 2020-04-26 08:25:01
	luckydude: 2020-04-24 18:57:55 Very good Question, Learnt a lot from this question.
	fighter_4: 2020-04-22 08:59:57 Guys plzzzzz keep the size of the tree array atleast 3 or 4times of n, it costed me a whole day to figure it out, then it will pass the test case 9 also enjoy!!!
	sagarnikamf72: 2020-04-14 11:24:14 We need to print maximum sum of elements of a (contiguous)subarray A[ i.......j] such that x <= i <= j <= y and not the maximum element in range [x, y] !!!!! Read question carefully if getting WA
	aryan__0406: 2020-04-09 19:34:19 @randomtree you have written wrong code that's why you are getting wrong answer. Also using brute force approach will give time limit exceeded. Learn segment tree for this.

Submit solution!

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