Chef and Easy Problem
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given a sequence A1, A2, ..., AN and Q queries. In each query, you are given two parameters L and R; you have to find the smallest integer X such that 0 ≤ X < 231 and the value of (AL xor X) + (AL+1 xor X) + ... + (AR xor X) is maximum possible.
Note: xor denotes the bitwise xor operation.
- The first line of the input contains two space-separated integers N and Q denoting the number of elements in A and the number of queries respectively.
- The second line contains N space-separated integers A1, A2, ..., AN.
- Each of the next Q lines contains two space-separated integers L and R describing one query.
For each query, print a single line containing one integer — the minimum value of X.
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- 0 ≤ Ai < 231 for each valid i
Subtask #1 (18 points):
- 1 ≤ N ≤ 103
- 1 ≤ Q ≤ 103
- 0 ≤ Ai < 210 for each valid i
Subtask #2 (82 points): original constraints
Input: 5 3 20 11 18 2 13 1 3 3 5 2 4 Output: 2147483629 2147483645 2147483645
|Tags||easy-medium, hruday968, march18, prefix-sum, xor|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.