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
|
fardin_abir:
2019-11-04 08:57:03
Solved it using segment tree, main challenge is merging two node... and avoid returning zero from unnecessary nodes, it causes WA in test case 9. |
|
gabadzeluka:
2019-10-28 14:46:53
Solved it!!! if u have wrong answer on 9th test case try this (all negative):
|
|
manuver:
2019-10-15 08:06:39
for WA on 9 Test case:
|
|
wingman__7:
2019-10-10 08:51:38
I went through all the comments, everyone is talking about Kadane's algo but time complexity of Kadane's algo is O(n) and if we answer "m" queries total time complexity will become O(m*n). The problem setter has fixed the time limit and value of "m" such that the 9th test case will fail. You have to implement segment tree, then the total time complexity will be O(m*logn). |
|
mriow:
2019-09-25 12:26:57
For some reason i got 1.42 seconds but the submission was accepted... |
|
rahulsinghk:
2019-09-17 18:57:31
what is 9th test case??
|
|
ajv123:
2019-09-12 17:36:59
Does someone know what the 9th test case is?
|
|
nprakhar:
2019-08-21 13:20:23
Even after using Kadane's Algorithm with fast I/O I'm geeting TLE on test 9.... |
|
|
nprakhar:
2019-08-21 12:57:22
I used Divide and Conquer Approach for this problem so Time Complexity is O(m*n*logn). I'm getting TLE in test 9. Any better approach? |
|
chirayu_555:
2019-08-20 17:36:21
Segment tree with little bit of analysis on node gives desired result. AC in single go..!! |
| 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