Hello, codeforces!

Recently I came up with a task, but I couldn't solve it.

The task is:

You are given a two arrays a and b of size n (1 ≤ n ≤ 10⁵). You should answer q (1 ≤ q ≤ 10⁵) queries:

• for given integer k (1 ≤ k ≤ n) you need to find maximal value a_i + b_k - i.

Всем привет!

Как вы, наверно, знаете доступ/добавление/удаление в хэш-таблице работает за O(1). Сегодня мы попытаемся улучшить эту оценку. Теперь рассмотрим реализацию хэш-таблицы с закрытой адресацией: пусть функция h равновероятно переводит каждый элемент множества A в множество B, те h: A → B, где A — множество возможных значений, а B — первые k натуральных чисел, для просты возьмем k = |A|. Если жи есть два элемента x, y для которых h(x) = h(y), то будем добавлять их в цепочку ячейки h(x) для разрешения коллизий. Вообще раз O оценка — это оценка сверху, то давайте далее полагать, что в каждую такую ячейку попадет t = 1 элементов. Тогда изменим способ хранения элементов со списка на set, но мы знаем, что время работы операций в set есть , но так как размер нашей ячейки t, то операции работают за , отсюда получаем, что n операции на нашей хэш-таблице отработают за O(n·0) = O(0).

Отправляю код по задаче Е, который как говорит сайт для подсчета символов, содержит 65012 символов, но на кфе пишет, что "Поле должно содержать не более, чем 65535 символов".