Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
||||||
2016-08-13 01:07:55
@What Does The Fox Say? my code uses mo's with multiset its getting tle on test case 10 time complexity n *(rootn)*logn submission id:17493739 i tried changing mo's block size to 4 rootn and 2 root n but still tle -- setter -- - STL containers' complexity have high constant factors, use other structures or optimize them. Last edit: 2016-08-13 18:03:37 |
||||||
2016-07-16 00:41:00 shikhar jindal
someone plzz provide me some tricky testcases. |
||||||
2016-02-01 14:56:04 the_imp
@What Does The Fox Say? I have a running time of O(N*SQRT(N)*LOG(N) but tle on the 8th test case. what is the expected time complexity? submission id:16208276 -- setter -- : - O(N * sqrt(N) * log(N)) should be able to pass the time limit. - Your segment tree implementation should be optimized more to pass the time limit. Last edit: 2016-02-03 09:09:45 |
||||||
2015-07-29 21:17:55 Rishit Sanmukhani
Nice question :) Those getting wrong answer try this: 4 1 1 -1 1 -1 1 4 Correct Answer: 4 |
||||||
2015-06-17 22:20:57
I am using MO's algorithm and getting right answer for all test cases I have tested but still getting WA.Somebody please have a look. Last edit: 2016-01-11 14:47:06 |
||||||
2015-05-22 15:42:48 ashish kumar
Why my code gives always wrong answer however i tested it on so many random test cases ? code id is 14300007 |
||||||
2015-03-31 14:02:15 Xsquare
Hey, wont MO's algorithm of complexity O(N*SQRT(N)*LOG(N)) get AC!? |
||||||
2014-12-31 16:44:49 ISHANI
MO's algorithm and simple one. |
||||||
2014-09-30 15:42:31 kelaseek
check why i am getting wrong answer? i used balanced bst's to search for intervals time is pretty decent . checked it with 50000 random intervals both brute force and my solution are giving the same results .please give some example test cases where my solution fails Answer: Try creating a brute-force solution and compare the results. Answer 2: 4 1 1 -1 1 -1 1 4 oh thanks it seems i didnt properly understand the question Last edit: 2014-10-02 08:12:29 |
||||||
2014-09-24 17:24:36 mark03
An hard one! BTW I learned something new about sqrt-decomposition/Mo's algorithm :) |