Nikitosh and xor
All submissions for this problem are available.
Nikitosh the painter has a 1-indexed array A of N elements. He wants to find the maximum value of expression
(A[l1] ⊕ A[l1 + 1] ⊕ ... ⊕ A[r1]) + (A[l2] ⊕ A[l2 + 1] ⊕ ... ⊕ A[r2]) where 1 ≤ l1 ≤ r1 < l2 ≤ r2 ≤ N.
Here, x ⊕ y means the bitwise XOR of x and y.
Because Nikitosh is a painter and not a mathematician, you need to help him in this task.
The first line contains one integer N, denoting the number of elements in the array.
The second line contains N space-separated integers, denoting A1, A2, ... , AN.
Output a single integer denoting the maximum possible value of the given expression.
- 2 ≤ N ≤ 4*105
- 0 ≤ Ai ≤ 109
- Subtask 1 (40 points) : 2 ≤ N ≤ 104
- Subtask 2 (60 points) : Original constraints
Input: 5 1 2 3 1 2 Output: 6
Choose (l1, r1, l2, r2) = (1, 2, 3, 3) or (1, 2, 4, 5) or (3, 3, 4, 5).
|Tags||bitwise, rebryk, sept15, trie, xor|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.