MarioYC's blog

Codeforces 85D using vector
By MarioYC, 14 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

»
14 years ago, hide # |
 
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