std::set и вопрос про его работу с памятью

Revision ru1, by ferc, 2016-06-28 11:58:11

На последнем контесте была задача D. Кай и снежинки. В разборе написано, что вполне подойдет решение в каждой вершине сливать сеты ее потомков.

Очевидно, что худший тест — это просто цепь из 300000 вершин. Тогда получается, что в каждой вершине будет 1, 2, 3,..., 300000 элементов в сете. Всего элементов (арифм. прогрессия) 300000 * 300000 / 2 ~= 45 * 10^9.

Это катастрофически много. Когда я попытался именно сохранить все эти сеты, то, разумеется, получил ML. Однако, если написать как в разборе, то есть просто запуститься рекурсивно из корня и постепенно получать ответ для него (не сохраняя сами сеты), то получим Accepted.

Так вот по сути же выделяем под те же 45 * 10^9 интов. Единственное, что приходит в голову, то что сет после выполнения функции чистит за собой память, которую потребовал в ходе выполнения этой функции, и в последствии может снова использовать ее же.

1) Подскажите, это правда так?

Грубо говоря, есть цикл for (int i = 0; i < 100000; i++) { set a; a.insert(3); }

Правда ли, что потребуется памяти столько, сколько необходимо на одну итерацию? Я просто раньше думал, что выделяется всегда абсолютно новая область памяти. Помогите разобраться, пожалуйста.

Tags выделение памяти, память, работа с памятью, memory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian ferc 2016-06-28 11:58:11 1318 Первая редакция (опубликовано)