| Submit | All submissions | Best solutions | Back to list |
ZQUERY - Zero Query |
| English | Vietnamese |
Cho một dãy số gồm N phần tử, mỗi phần tử bằng -1 hoặc 1.
Có M truy vấn, mỗi truy vấn gồm hai số L và R, bạn cần tìm độ dài của dãy con liên tiếp dài nhất trong phạm vi từ L đến R (gồm cả L và R) mà có tổng bằng 0.
Input
Dòng đầu tiên chứa hai số nguyên N và M (1 <= N, M <= 50000) - số lượng phần tử của dãy số và số lượng truy vấn.
Dòng thứ hai chứa N số - các phần tử của dãy số, mỗi phần tử bẳng -1 hoặc 1.
Trong M dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 <= L <= R <= N).
Output
Với mỗi truy vấn, in ra độ dài của dãy số dài nhất thoả mãn yêu cầu. Nếu không có dãy nào phù hợp, in ra 0.
Ví dụ
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
|
||||||
|
2021-02-07 12:57:47
stO provicy Orz |
||||||
|
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 and try this test: 4 1 1 1 -1 1 3 4 ans=2 |
||||||
|
2018-01-06 12:59:39 DOT
Woah! Took so much of time trying to fix minor bugs. Finally AC. :) People trying to build up on QCHEF solution, ensure you're handling the number before the start of the current block as well. |
||||||
|
2017-11-04 21:45:06 shubham
Problem can be reduced to https://www.codechef.com/problems/QCHEF |
||||||
|
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; |
||||||
|
2017-07-31 15:38:24
Really interesting problem. Can be solved without MO :) |
||||||
|
2017-06-29 07:20:49
what will be the answer for this 6 1 -1 1 1 1 1 -1 1 6 answer must be 2 isn't it? but the AC solution giving answer 4 and still AC how??? Last edit: 2017-06-29 07:21:40 |
||||||
|
2017-02-01 20:38:43 _________++++__________
Great question to understand MO algorithm |
||||||
|
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. Problem code: 17951896 I'm using MO's algorithm and summing. Last edit: 2016-10-17 12:01:17 |
||||||
|
2016-08-15 14:48:20 ziadxkabakibi
Nice One ! can be solved using mo and binary search :D |
||||||
RSS