Я часто видел как в задачах кто-то сдавал простое решение за $$$O(n^2)$$$, хотя авторы этого явно не хотели. Обычно секрет в том, чтобы писать код, который хорошо векторизуется (использует всякие SIMD инструкции), но без опыта делать это получается плохо, потому что нет интуиции, что будет работать быстро, а что нет.

Когда я увидел задачу 1701F - Points и TL=6.5с решил, что это отличный шанс с одной стороны написать решение за квадрат, которое получит AC, а с другой — записать сам процесс оптимизации кода, вдруг кому-то будет интересно.

Получилась вот такая статья, надеюсь кому-нибудь будет интересно. Там довольно много вещей, которые специфичны только для Rust, но я думаю, что в С++ есть аналогичные проблемы/решения.

А еще подписывайтесь на мой канал в Telegram, чтобы у меня была мотивация писать что-то еще. Там скорее всего будет не только про олимпиады, а в целом про программирование.

P.S. надеюсь на CF не банят за саморекламу :)