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
Sarthak Munshi:
2015-10-08 17:34:55
Be careful! You don't have to find the max element in the range . You have to find maximum subvector sum in the range . i . e if array is {1,2,-4,1}......answer should be 3 because 1+2>than all combinations added together linearly . |
|
Aayush:
2015-10-02 19:36:38
I am suffering in judge 9. Getting WA. I am using ST concept and I am confident with my logic.
|
|
Oasis:
2015-09-28 18:16:14
Very Good Question! My second segment tree problem :D |
|
dev:
2015-09-16 09:11:40
Finally Ac after too many wa and sigsev ...had to comment ! worth trying...learnt a lot...used seg tree !! :) |
|
kamjpvv4m7:
2015-09-12 09:52:11
Time is limited so never use "cin" and "cout" |
|
elise:
2015-09-08 02:13:16
No need to use lazy propagation, no need to use long long int.
|
|
theweblover007:
2015-09-07 18:40:16
Is lazy propog. required to solve this ? |
|
Pratik S:
2015-08-27 19:23:29
M in long long int(C++)?
|
|
PKJ:
2015-08-22 13:08:15
Note that the answer to a query could even be negative. |
|
hnvahidi:
2015-08-12 01:35:48
i don't get it :|
|
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 |