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
|
killshot667:
2020-12-25 21:12:17
Finally got it in second try . Good beginner question for segment trees. |
|
ashu_3916:
2020-12-22 11:53:30
finally done !! please check constraints , dont return INT_MIN in base condn of query part as |A[i]| ≤ 15007 , so keep that in mind. (later in code INT_MIN+INT_MIN can lead u to wrong answers )
|
|
salonix__9:
2020-11-19 14:37:33
IF you are getting TLE, use the binary search technique in the query function |
|
sparsh_351:
2020-11-11 17:16:44
problem nzec error using python
|
|
prashant2016:
2020-11-07 13:10:14
There can't be empty subarray as answer. #Corner Case |
|
asifali_11:
2020-10-01 12:28:27
how to get the input of test case 8 |
|
sarkybastard:
2020-09-24 23:26:05
TLE in 9th Test Case? Then you don't know how spoj works. |
|
kapilsukrit2:
2020-09-24 09:17:17
OK. So here is the thing->
|
|
saurabh_shinde:
2020-09-10 12:40:31
Refer codeforces EDU series for the anwer |
|
yagnik_da175:
2020-09-04 15:10:00
You have to write merge fuction carefully. |
| 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