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
vaifai:
2018-03-09 13:57:55
TL is very strict for JAVA. |
|
nadstratosfer:
2018-02-25 06:42:01
pykay, probably blanklines somewhere in the input. You're wasting your time anyway, problems from this series have TL too tight for Python solution to pass. |
|
pykay:
2018-02-23 19:22:45
test case 9 run time error(python 3.5). any suggestions? |
|
chaitya62:
2018-02-21 16:51:50
I don't understand why I am getting a TLE, I am using scanf, printf, using bit manipulation for multiplication and division. |
|
satyampnc:
2018-02-01 20:55:19
use long long int :)
|
|
sherlock11:
2018-01-31 07:23:46
use scanf and printf for AC........
|
|
akashgupta13:
2018-01-28 17:44:13
no constraints for queries? |
|
viniet_sw:
2018-01-26 12:50:52
badia question hai madarjaat |
|
eicaptain:
2018-01-26 02:01:51
This problem can also be solved by dsu with complexity O(n alpha(n)) |
|
coolio_1:
2018-01-18 20:21:00
Assume 1 based indexing for the input array as well as the queries. So the input array will be from [1...n]. Cost me a couple of WA! :( |
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 |