Блог пользователя MarioYC

Codeforces 85D using vector
Автор MarioYC, 14 лет назад, По-английски
I was reading to levlam's code for Codeforces 85D (Sum of Medians) :  http://pastie.org/3224822 

It is nice how he does insertion and elimination of elements in O(lg n) by using lower_bound, but I can't understand why the code passes since it has complexity O(n / 5) for each sum query. Could someone explain why it passes?

By n I mean the number of elements currently stored at the vector.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
He does not make operations insert and delete in O(log(n)), vector<int>::insert(interator, value) is O(n), erase operation also is O(n). His solution is O(n^2), He is very lucky, and the tests are weak
→ Ответить