decoder__'s blog

By decoder__, history, 4 years ago, In English

Here is my code https://codeforces.com/contest/681/submission/91075066 for the question https://codeforces.com/problemset/problem/681/C. Can anyone help me that use of which thing is causing the MLE and which data structure should be used to avoid MLE?

  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Use a multiset or a priority queue. Insert and removeMin are straightforward now.

For getMin, keep on removing the smallest element and keep on incrementing the count until the removed element is smaller than the getMin output given.

If now, the multiset is empty or the smallest element in it is greater than the getMin output given increase count by 1 (it accounts for adding the getMin output given by an insert operation).