eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Fast Squarier Transform

Fast Squarier Transform

You are given two arrays of integers $[a_1, a_2, \dots, a_n]$ and $[b_1, b_2, \dots, b_m]$. Find the following value: $$ \sum_{i = 1}^n\sum_{j = 1}^m \lfloor \sqrt{|a_i - b_j|} \rfloor. $$ Note that $\lfloor x \rfloor$ denotes the maximum integer not exceeding $x$, and $|x|$ denotes the absolute value of $x$. \InputFile The first line of the input contains $2$ integers $n, m$ ($1 \leq n, m \leq 10^5$). The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i$, $a_1 + a_2 + \ldots + a_n \le 2\cdot 10^7$). The third line of the input contains $m$ integers $b_1, b_2, \dots, b_m$ ($0 \le b_i$, $b_1 + b_2 + \ldots + b_m \le 2\cdot 10^7$). \OutputFile Print a single integer --- the sum from the statement. \Note In the first sample the answer is $\lfloor \sqrt{|1 - 2|} \rfloor + \lfloor \sqrt{|1 - 3|} \rfloor = \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor = 1 + 1 = 2$. In the second sample, the answer is $\lfloor \sqrt{|1 - 3|} \rfloor + \lfloor \sqrt{|1 - 4|} \rfloor + \lfloor \sqrt{|1 - 5|} \rfloor + \lfloor \sqrt{|2 - 3|} \rfloor + \lfloor \sqrt{|2 - 4|} \rfloor + \lfloor \sqrt{|2 - 5|} \rfloor = $ $ \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor + \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor = 1 + 1 + 2 + 1 + 1 + 1 = 7$.
Лимит времени 2 секунды
Лимит использования памяти 256 MiB
Входные данные #1
1 2
1
2 3
Выходные данные #1
2
Входные данные #2
2 3
1 2
3 4 5
Выходные данные #2
7
Автор Anton Trygub
Источник All-Ukrainian Collegiate Programming Contest 2021-2022, II stage