| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 35 | 20 | 18 | 54.545% |
You are given an array of integers $A$ of size $N$ (indexed from $1$ to $N$) where $A_i$ is either $0$, $1$, $2$, or $3$.
A subarray $〈l, r〉$ of $A$ is defined as $[A_l , A_{l+1}, \cdots , A_r]$, and its size is $r - l + 1$.
A value $x$ is the only mode of a subarray $〈l, r〉$ if and only if $x$ appears strictly more often than other values in subarray $〈l, r〉$.
Your task in this problem is to find, for each $x ∈ \{0, 1, 2, 3\}$, the size of the longest subarray of $A$ such that $x$ is the only mode of that subarray, or determine if $x$ cannot be the only mode in any subarray.
Input begins with an integer $N$ ($1 ≤ N ≤ 100\, 000$) representing the size of array $A$. The next line contains $N$ integers $A_i$ ($A_i ∈ \{0, 1, 2, 3\}$).
Output four space-separated integers in a single line. Each integer represents the answer where $x$ is $0$, $1$, $2$, and $3$, respectively. For each value of $x$, if there exists a subarray such that $x$ is the only mode in that subarray, then output the size of the longest subarray; otherwise, output $0$.
7 1 2 2 0 3 0 3
4 1 5 3
12 2 0 1 0 2 1 1 0 2 3 3 3
4 9 1 9
2 0 2
1 0 1 0
The longest subarray such that $0$ or $2$ is the only mode contains only a single element by itself; on the other hand, there is no subarray such that $1$ or $3$ is the only mode.
12 3 0 2 2 1 0 2 1 3 3 2 3
1 5 11 8