D - Sum of Min of Xor Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 (A_1,A_2,\cdots,A_N) および (B_1,B_2,\cdots,B_N) が与えられます．

\sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j) の値を求めてください． ただしここで，\oplus はビットごとの排他的論理和を表します．

制約

  • 1 \leq N \leq 250000
  • 0 \leq A_i,B_i < 2^{18}
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

答えを出力せよ．

入力例 1

3
1 2 3
4 5 6

出力例 1

4
  • \min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
  • \min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
  • \min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1

よって，答えは 1+2+1=4 になります．

入力例 2

4
1 2 3 4
1 2 3 4

出力例 2

24

入力例 3

10
195247 210567 149398 9678 23694 46151 187762 17915 176476 249828
68649 128425 249346 62366 194119 117620 26327 161384 207 57656

出力例 3

4019496

Score : 700 points

Problem Statement

Given are sequences of N integers each: (A_1,A_2,\cdots,A_N) and (B_1,B_2,\cdots,B_N).

Find \sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j), where \oplus denotes the bitwise XOR.

Constraints

  • 1 \leq N \leq 250000
  • 0 \leq A_i,B_i < 2^{18}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

Print the answer.

Sample Input 1

3
1 2 3
4 5 6

Sample Output 1

4
  • \min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
  • \min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
  • \min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1

Thus, the answer is 1+2+1=4.

Sample Input 2

4
1 2 3 4
1 2 3 4

Sample Output 2

24

Sample Input 3

10
195247 210567 149398 9678 23694 46151 187762 17915 176476 249828
68649 128425 249346 62366 194119 117620 26327 161384 207 57656

Sample Output 3

4019496