ZQUERY - Zero Query
English | Vietnamese |
Given an array having N elements, each element is either -1 or 1.
You have M queries, each query has two numbers L and R, you have to answer the length of the longest subarray in range L to R (inclusive) that its sum is equal to 0.
Input
The first line contains two numbers N and M (1 <= N, M <= 50000) - the number of elements and the number of queries.
The second line contains N numbers - the elements of the array, each element is either -1 or 1.
In the next M lines, each line contains two numbers L and R (1 <= L <= R <= N).
Output
For each query, print the length of the longest subarray that satisfies the query in one line. If there isn't any such subarray, print 0.
Note
Subarray in an array is like substring in a string, i.e. subarray should contain contiguous elements.
Example
Input: 6 4 1 1 1 -1 -1 -1 1 3 1 4 1 5 1 6 Output: 0 2 4 6
hide comments
Jashan Goyal:
2014-09-17 23:54:21
@What Does The Fox Say? I have optimized my code to O(N).Please see to my submission id 12234553.I am still getting TLE.
|
|
S.Y.P.Lai:
2014-09-17 23:54:21
What should I do if the result is "wrong answer", but all my own test cases show the code is correct?
|
|
S.Y.P.Lai:
2014-09-17 23:54:21
Looks like straight forward ways are not going to be accepted. I will keep trying. Is there any way to check the actual timings other than the standard "TLE" message?
|
|
VictorWonder:
2014-09-17 23:54:21
@What Does The Fox Say? I have thought about a solution which is O(n log^2n),But it didn't work during the limited time in my computer.So I want to know if there is a solution which is less than mine?
|
|
What Does The Fox Say?:
2014-09-17 23:54:21
I have added the 'note' section because I saw many people misunderstand the problem. Last edit: 2014-08-10 07:23:09 |
|
Kanish_The_Vista:
2014-09-17 23:54:21
@What Does The Fox Say? can see my submission id 12113048 .why i am getting tle i think so my sol. time complexity is less than O(n).
|
|
wisfaq:
2014-09-17 23:54:21
There must be something wrong with the testfiles.
|
|
mehmetin:
2014-09-17 23:54:21
Are the test files correct? And it is subarray, not subsequence, isn't it?
|
Added by: | What Does The Fox Say? |
Date: | 2014-08-07 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |