SPOJ.com - Problem ZQUERY

ZQUERY - Zero Query

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

Submit solution!

hide comments

< Previous 1 2 3 Next >

	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. Answer: You still have running time of O(n) per query. Last edit: 2014-08-26 04:13:08
	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? Edit: OK, I found the problem... Last edit: 2014-08-24 10:13:40
	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? Answer: Try creating a random testcase and measure the running time on your computer. Just made a 50000 M 50000 N testcase and my code ran near 1 minute. I still have a long way to go... Last edit: 2014-08-21 19:35:24
	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? Answer: I would say that my solution is not better than O(nlog^2n). If your solution really runs in O(nlog^2n), it should get AC. Oh,I think there must be some mistakes in my code and I should check it.And thanks very much for your answer. Last edit: 2014-08-12 01:53:45
	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). Answer: The 'for' loop in your 'while' loop runs in O(n), so the total complexity is O(mn). @PS :- thanks can you tell me the what is expected time complexity Answer: It should be less than O(mn). @PS Thank You Last edit: 2014-08-10 09:38:34
	wisfaq: 2014-09-17 23:54:21 There must be something wrong with the testfiles. If I run m queries I get NZEC, if I run m-1 queries I get TLE (and that's not so strange, as my prog isn't that clever for now, but I didn't want to invest too much time seeing that up till now nobody succeeded in getting AC. Coming back to this problem when I see that it's possible to get AC) PS: Sorry for the inconvenience, it seems that the first query is on the 2nd line. I will fix this. PS: I have fixed the test files and rejudged your submissions. Last edit: 2014-08-09 18:07:15
	mehmetin: 2014-09-17 23:54:21 Are the test files correct? And it is subarray, not subsequence, isn't it? PS: Yes, it is subarray. Last edit: 2014-08-08 10:58:14

Submit solution!

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