MarioYC's blog

Codeforces 85D using vector
By MarioYC, 12 years ago, In English
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.
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Well weak tests explain it, thanks.
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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...
      → Reply