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

Codeforces 85D using vector
Автор MarioYC, 13 лет назад, По-английски
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
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 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
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Well weak tests explain it, thanks.
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      And fast codeforces servers, and array of size 512 kb can be placed in L1 processor's cache, and some processor's optimisations while copying an array...
      → Ответить