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
|
const_variable:
2019-08-03 13:53:34
I'm getting TLE even after using basic segment tree function. What part can I improve on?
|
|
s_h_i_1:
2019-07-27 09:28:23
use segment tree . |
|
scolar_fuad:
2019-07-12 05:37:14
I am getting WA on 9th test case and why is there anyone like me ? |
|
landofkings:
2019-07-01 01:27:54
if getting wa, try to find bug in query. for extreme cases it must be like .
|
|
sagarrawat:
2019-06-28 19:09:56
finally, AC (Segment tree + fast i/o in java) Last edit: 2019-06-28 19:10:32 |
|
inderjeet_333:
2019-06-18 09:56:02
@Kesh getting wa on 9th test case .
|
|
kanishk779:
2019-06-13 13:15:49
@somanshu_s what is the meaning of prefix sum and suffix sum and total sum in this problem. |
|
pan1640616850:
2019-06-05 05:29:38
if you use long long,you will AC! |
|
chypsd:
2019-06-03 09:47:48
GOT TLE
|
|
kesh4281:
2019-05-31 09:48:29
for WA on 9th--
|
| 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