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
|
testing java:
2016-08-23 18:58:00
The time limit is absurd. Still don't know whether I have some coding errors or my java is simply too slow to make it through.
|
|
davidgalehouse:
2016-08-23 08:26:22
Note to C# solvers: This is a really good problem to learn segment trees (don't use wikipedia as a reference, I recommend http://wcipeg.com/wiki/Segment_tree). Unfortunately, there are some annoying little issues. Use StringSplitOptions.RemoveEmptyEntries (or maybe just Trim?) to avoid runtime error. Use string builder and a single Console.Write(). And just in case, beware a bug in the Mono compiler about invalid IL code generation (I got this when doing multiple assignment inside of a constructor, like PropA = PropB = value). Last edit: 2016-09-25 20:57:40 |
|
xunx:
2016-08-09 11:41:47
getting TLE which data structure shall I use? |
|
giriprasad kemburu:
2016-07-29 21:50:07
Using bufferedreader causes NZEC.Can anyone tell me how to fix this problem.It works fine on my ide and some other problems also works fine with scanner but not with bufferedreader. |
|
Mohamed Elnaggar:
2016-07-25 12:56:49
I cant Expect What is The Wrong ?
|
|
flyingduchman_:
2016-07-21 14:16:15
Took almost one month to get accepted |
|
naksh9619:
2016-07-19 02:00:07
good problem :) Last edit: 2016-07-19 22:32:40 |
|
baadshah_:
2016-06-26 14:15:48
Finally AC took whole DAY!! |
|
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?
|
| 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