Я часто видел как в задачах кто-то сдавал простое решение за $$$O(n^2)$$$, хотя авторы этого явно не хотели. Обычно секрет в том, чтобы писать код, который хорошо векторизуется (использует всякие SIMD инструкции), но без опыта делать это получается плохо, потому что нет интуиции, что будет работать быстро, а что нет.
Когда я увидел задачу 1701F - Точки и TL=6.5с решил, что это отличный шанс с одной стороны написать решение за квадрат, которое получит AC, а с другой — записать сам процесс оптимизации кода, вдруг кому-то будет интересно.
Получилась вот такая статья. Там довольно много вещей, которые специфичны только для Rust, но я думаю, что в С++ есть аналогичные проблемы/решения.
А еще подписывайтесь на мой канал в Telegram, чтобы у меня была мотивация писать что-то еще. Там скорее всего будет не только про олимпиады, а в целом про программирование.
P.S. надеюсь на CF не банят за саморекламу :)
Спасибо за интересную статью!
Я тоже пытался упихать квадрат в этой задаче на C++, однако видимо что-то пошло не так, и что бы я ни делал (сначала надеялся на авто-векторизацию, потом начал сам векторизовывать код с помощью x86intrin), посылка получала TLE на тесте с n = 200k, d = 100k.
Видимо, дело в том, что мой квадрат уж слишком неоптимален :/
Как минимум одно отличие (о котором я забыл упомянуть в статье) в том, что у меня еще есть сжатие координат.
С одной стороны кажется, что координаты и так до $$$2 \cdot 10^5$$$, и их сжимать не нужно. Но на самом деле можно сделать тест, на котором добавляют/убирают последнюю точку, и нужно обновить ответ для всего массива (получается ровно $$$N^2$$$ операций).
А если сделать сжатие координат, то на таком тесте массив будет всего из одного элемента и будет все работать быстро. А максимальным будет тест, в котором добавляют все точки по одному разу, который требует $$$N/2$$$ операций в среднем на одну точку. Получается оптимизация в два раза.
Как-то так на C++ за 3.6с: https://codeforces.com/contest/1701/submission/163664905
Из оптимизаций, что у тебя не было, сумму дельт я считаю в int32 и выгружая ее в ответ лишь раз в 10K итераций. Без этого 5с получается. С тернарным оператором выходит совсем немного хуже, 3.7с, но массив alive булевым, судя по всему, лучше не делать. upd. Не прав, можно делать, получается 2.9с: 163666755
Ага, прикольно. Чем-то напоминает оптимизацию, когда что-то считаешь по модулю, и вместо взятия по модулю каждый раз, делаешь это раз в несколько итераций пользуясь тем, что int64 не успел переполниться.
Кстати, эта статья во многом появилась благодаря сабмитам, которые видел от тебя в других задачах :)