6

Есть n массивов (n <= 10^5), k запросов (k <= 10^5).

Каждый запрос - это одно из двух действий:

  • объединить два массива
  • разделить массив на два новых (нацело поделить размер исходного)

Каждое действие порождает новый(-ые) массивы, для каждого нового массива необходимо выводить произведение всех элементов по модулю количества элементов в этом массиве. - (a1*a2*...*am)%m, где m - количество элементов в массиве.

Ограничения: по времени 2 секунды, по памяти 256 МБ.

Данная задача, безусловно, решается с помощью какой-либо персистентной структуры данных. Я попробовать решить с помощью персистентного декартово дерева (Treap, дерамида, называйте как хотите).

В структуре Node я добавил 2 новых поля: размер и ответ на запрос (модуль произведений). В итоге Node у меня весит 40 байт. Задача не проходит по памяти, примерно на 100-200мб :)

Скажите, возможно ли оптимизировать это решение, либо использовать другую структуру данных, если да то, то подскажите какую.

2
  • вы можете уточнить - n ("Есть n массивов") - это количество массивов или число элементов в одном массиве (a1*a2*...*an)%n)? 26 ноя 2017 в 21:36
  • 1
    @MaxU, спасибо, исправил
    – 9Pasha
    26 ноя 2017 в 21:43

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.