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
a000:
2018-05-23 23:38:29
savdhaan rahein, surakshit rahein, aur question sahi se padhein.
|
|
shubhank_7673:
2018-05-09 18:45:48
getting WA on TC 9 using sqrt decomposition. can anybody help? |
|
chawla_harsh:
2018-04-28 15:13:14
Can anyone help with case 9?
|
|
thanos_tapras:
2018-04-26 13:23:35
getting WA in testcase no9. I use long long int and scanf/printf. Anybody help?
|
|
sanjeev:
2018-04-05 12:34:56
this is the problem where you can spend time to learn the concepts. |
|
alysalhab5:
2018-03-26 22:12:01
Testcase 9 gives TLE :( |
|
sktibrewal:
2018-03-24 18:38:00
Use fast i/p. |
|
siddsoj_5444:
2018-03-22 16:29:58
used SEG trees ... still wrong answer on TC 9 anyone got passed ... please help
|
|
siddsoj_5444:
2018-03-22 16:23:36
@ista2000 what do you return in case of no overlap? tag me please |
|
riddhyasona:
2018-03-21 18:06:59
zenosama is awesome. Last edit: 2018-04-03 10:45:48 |
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 |