In Problem D-Bandit in a City (Codeforces Round 678), the binary search solution has complexity of O(Nlog(2e14)), where N=2e5, So, it should take around 100ms, but most of submissions using binary search, like this are taking more than 900ms. Can anyone tell why is this happening?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.04.2026 09:29:16 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Probably significant amount of this time is input
I don't know expected performance of cin with magic incantations, but there are 400000 values to be read
If input is the problem, then the intended linear solution would also have taken large time.
Even taking 1e6 values will take no more than 50ms.
2e5 * log(1e14) = 1e7
Also there is a really big constant in front of it. There are lots of operations and there is recursion
Also there are lots of random jumps that may make processor caching ineffective
Also there is a huge input
I believe it is a combination of all those factors