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
|
Deepak :
2016-06-18 17:27:55
finally AC..great problem for beginners.thanks @AbhishekRajput |
|
oalieno:
2016-05-11 15:43:27
Did anyone use Treap to solve this problem?
|
|
mars_ch:
2016-05-02 08:34:46
同意楼上！！ |
|
yousiki:
2016-05-01 05:38:06
TL is too strict |
|
geekyadity:
2016-04-14 15:04:18
Use printf, scanf. ( sync_with_stdio(false) ) gives TLE with the same code |
|
a_b_c12345:
2016-04-10 09:16:53
yoo..!! after 2 WA and 2 TLE finally accepted. To get AC from TLE just changed input array and tree into global. |
|
minhthai:
2016-02-14 14:50:58
why hate java so much :((
|
|
Tomasz Plaskota:
2016-02-12 13:51:16
as mentioned before: make sure you use fast input output cause there is ALOT of that.
|
|
sanket407:
2016-02-05 14:27:47
FOR JAVA GUYS :
|
|
nib:
2016-01-25 10:38:20
Extremely strict TL. Same idea using struct passed, but using vector gets TLE :/ |
| 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 |
RSS