Привет, Codeforces! Кто-нибудь знает как написать до сверху так, чтобы оно потребляло 2n памяти? В интернете нашёл лишь реализации за 4n.
Привет, Codeforces! Кто-нибудь знает как написать до сверху так, чтобы оно потребляло 2n памяти? В интернете нашёл лишь реализации за 4n.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
Название |
---|
Автокомментарий: текст был обновлен пользователем Hardes1 (предыдущая версия, новая версия, сравнить).
Напиши неявное ДО на указателях. Вершин по определению создастся не больше 2n https://wiki.algocode.ru/index.php?title=Динамическое(Неявное)_Дерево_Отрезков
Я очень ценю твой вклад, но проблема в том, что один указатель занимает больше памяти, чем 1 int, например. Мне важно минимальное количество памяти и я слышал, что такая реализация с индексами есть...
Справедливости ради стоит сказать, что если использовать при отправке 32-битный компилятор, то указатель, как и int32 будет весить 4 байта. На codeforces таким компилятором является, например, Microsoft Visual C++ 2010.
И да я прекрасно понимаю, что в вершинах нужно хранить по два указателя, поэтому в любом случае выигрыша по памяти не будет.
Мне кажется, что компилятор MVC++ 2010 сейчас уже не в моде. К тому же я уточнил, что конкретно меня интересует и объяснил, почему твой вариант мне не подходит.
Реально
https://codeforces.com/blog/entry/65278?locale=ru
спасибо!