P
Хм.., спасибо. Попробую затестить.
Size: a a a
2020 July 15
AD
лучше разберись как работает, тогда в будущем сможешь с нуля сам написать
P
аа, ну да. Согласен, что вопрос не сложный был😱
Спасибо
Спасибо
DK
де вы последний раз видели задачу, которая сдаётся Фенвиком, но не сдаётся ДО?
2020, XIII Самарская областная межвузовская олимпиада по программированию, задача C. Манхеттенское расстояние
DK
военные учения 2.1
Эта задача сдается ДО, если листья сделать булевыми, а все остальные узлы - интами
K
Так тут дерево поиска с удалением должно прокатить
KK
2020, XIII Самарская областная межвузовская олимпиада по программированию, задача C. Манхеттенское расстояние
Красные пихают там до
DK
Так тут дерево поиска с удалением должно прокатить
Не пройдет по памяти
DK
Нужно 32 мбайта, а лимит 6 мб
K
Не пройдет по памяти
С ручным аллокатором
KK
Хотя при создании задачи подразумевалось, что до не должно заходить
DK
С ручным аллокатором
Вы сможете сделать 1млн узлов по 6 байт каждый?
K
Вы сможете сделать 1млн узлов по 6 байт каждый?
Вряд ли, только что увидел лимит по памяти
K
DK
Вряд ли, только что увидел лимит по памяти
Такие ограничения были сделаны чтобы O(N) все писали. Но, к сожалению, фенвик O(n log n) такими ограничениями не срезать по асимптотике
K
А, тут O(n) есть?
DK
Да. Когда я давал эту задачу второкурсникам, сразу двое написали O(n)
K
Да. Когда я давал эту задачу второкурсникам, сразу двое написали O(n)
Где преподаёте?
DK
Ну это были не обычные второкурсники, а те, кто ходят в кружок олимпиадного программирования, но дерево фенвика они не знали
DK
Где преподаёте?
РТУ МИРЭА