| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
||||||||||||||
|
2018-08-02 15:41:47
If you are getting TLE at testcase #9 instead of copy pasting the code submit your code file.You will thank me later. |
||||||||||||||
|
2018-08-01 19:06:04 DOT
1. To people getting WA for #9, ensure while computing the best in a range, you also check the elements individually. I missed that. 2. long long is not needed. int is enough for handling this condition (|A[i]| ≤ 15007 , 1 ≤ N ≤ 50000). Max value you can make is 15007 * 50000, well within the int range. 3. First seven cases are very weak. I misunderstood the question completely and was printing the max element in [l, r] and got WA only at #8. :P 4. Segment tree seems to be much faster than square root decomposition for this question Last edit: 2018-08-01 19:07:53 |
||||||||||||||
|
2018-07-24 14:38:13
Generally the suggestions in the comments are very good. One thing i would like to add is that even though most sites state that the segment tree array should be 2*N that is only true when N is a power of two, supposing a simple implementation of segment tree. Therefore a good size is 4*N. BTW a good testcase i found on SPOJtoolkit is the following : 9 324 3 23 -234 32 -4 324 435 -5775 3 1 4 3 5 5 9 |
||||||||||||||
|
2018-07-03 04:42:13
How to check ,in which test_case it's failing,I see everyone posting fails on TC 9,When I click on my submission it only shows WA |
||||||||||||||
|
2018-06-22 10:22:02
Looks like something wrong with the judge.. First try-- TLE on (9) --<no edit> second try--TLE on(7) --<no edit> third try --TLE on (9) --<no edit> fourth try-- whoa! AC this time !! Didn't understand what happened! |
||||||||||||||
|
2018-06-21 07:05:46
THOSE WHO HAVE PROBLEM WITH TESTCASE 9: I made a mistake in my code by considering that maxsum could be found only in prefix or suffix. It gave correct answer till TC8 . But TC 9 probably has a solution where max sum is contained in subarray. Check this case: Input: 6 -200 143 23 -231 123 33 1 1 6 correct output:166 But if you are not combining nodes properly, output:156(WRONG)... |
||||||||||||||
|
2018-06-13 20:08:48
feels good!! nice one scanf printf will work |
||||||||||||||
|
2018-06-13 19:26:07
i am getting WA on TC 9 any hint will be very helpful.Thanks |
||||||||||||||
|
2018-06-10 11:49:42
FOR THE ONES GETTING TLE/WA ON JUDGE - 9 : 1) RETURN - MAX_INT IN CASE OF NO OVERLAP 2) USE FAST I/O 3) USE LONG LONG |
||||||||||||||
|
2018-06-09 09:38:15
@thanos_tapras Thanks bro, reading comments helps ;) #was struck with the same problem |
||||||||||||||
RSS