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
|
oclewx:
2018-01-17 18:37:39
first time i got runtime error (SIGSEGV) , then TLE then WA and finally AC
|
|
manvscode:
2018-01-07 15:15:58
@geek_lady take i=1 and j=1 (assuming 0-indexing in array) we get sum =2.
|
|
excursionist:
2018-01-02 18:21:34
Testcase 9 gives TLE :( |
|
senacoder111:
2018-01-02 16:17:58
must if you want to learn segment tree |
|
vsr625:
2017-12-22 12:39:21
No, you should get 118 as answer
|
|
m2do:
2017-12-22 12:23:07
what would be the output of the following case? someone, please explain. My code gives 123 as output, am I correct?
|
|
somanshu_s:
2017-12-09 22:12:53
Hint for this problem : Build segment tree on this structure :
|
|
bash_turtle:
2017-12-04 18:05:00
i am getting a runtine error (SIGSEGV ).Can someone help please
|
|
manuparmar35:
2017-11-29 16:38:04
really a difficult problem someone please explain how can it be solved |
|
geek_lady:
2017-11-15 21:34:41
i donot get given testcase .
|
| 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