ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1306. Медиана последовательности

multiset VS priority_queue
Послано JackVoo 6 дек 2010 15:15
I use the multiset initially with the similar method. However, I had a memory limit exist. After, I saw the discussion, then I change the container to priority_queue.
Then I am able to solve the quetion. I just wonder, why with the similar algorithm, the memory usage is different? 1 396 KB vs 972 KB.

The memory usage of multiset is more than simple array is used then sorted. 1 084 KB
Re: multiset VS priority_queue
Послано Ruslan Nigmatullin [Ural FU] 19 дек 2010 18:11
multiset uses Red-Black Tree data structure, so it stores for every element not only it's value (4 bytes), but also addresses of it's parent (4 bytes more), both children (8 bytes) and color (enum, 4 bytes). So, as you can see, it spends 28 bytes for every element versus 4 bytes at priority_queue