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
leapfrog:
2021-02-07 12:57:47
stO provicy Orz |
|
evoiz963:
2019-02-27 22:26:10
good one but when i use set my code take to match but it get ac when i use dequeue it take lease time but it's still to big i think best idea to implement container that help you in this problem
|
|
DOT:
2018-01-06 12:59:39
Woah! Took so much of time trying to fix minor bugs. Finally AC. :)
|
|
shubham:
2017-11-04 21:45:06
Problem can be reduced to
|
|
starbot:
2017-10-10 21:36:26
@What Does The Fox Say? my submission id 20336783 is getting tle...However i think my solutions complexity is O(M*root(N)*Log(N))...could please look into it; |
|
mahmud2690:
2017-07-31 15:38:24
Really interesting problem. Can be solved without MO :) |
|
rajeev_899:
2017-06-29 07:20:49
what will be the answer for this
|
|
_________++++__________:
2017-02-01 20:38:43
Great question to understand MO algorithm |
|
titanlord89:
2016-10-17 12:00:40
Someone please have a look at my code. It WAs even though it passes everything I throw at it.
|
|
ziadxkabakibi:
2016-08-15 14:48:20
Nice One ! can be solved using mo and binary search :D |
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 |