시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 17 | 11 | 10 | 66.667% |
Consider an array of $k$ integers $b_1, b_2, \ldots, b_k$. Let $x \oplus y$ be the bitwise exclusive OR of $x$ and $y$. We shall say the linear power of the array $b$ is $$\mathit{LP} (b) = \max\limits_{i = 0, 1, \ldots, k} (b_1 \oplus \ldots \oplus b_i) + (b_{i + 1} \oplus \ldots \oplus b_k)\text{.}$$
You are given an array $a$ of $n$ integers. Find the linear power of all its prefixes.
The first line contains a positive integer $n$ ($1 \le n \le 10^6$), the length of the array.
The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^6$).
Output a single line containing $n$ space-separated integers: $\mathit{LP} (a_1)$, $\mathit{LP} (a_1, a_2)$, $\ldots$, $\mathit{LP} (a_1, a_2, \ldots, a_n)$.
5 1 2 3 4 5
1 3 6 10 9
10 11 13 14 14 9 8 0 10 10 7
11 24 20 24 15 23 23 17 23 30