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

Vector Implementation gives TLE/MLE where as Set implementation Gives AC.
Автор huzaifa242, история, 6 лет назад, По-английски

In past few days I have faced this problem very frequently. Implementing same Logic with set gives AC where as vector implementation gives TLE OR MLE.

Question 1

TLE Solution

AC Solution

I just changed the set implementation to set in order to check the running time.

Question 2

MLE Solution

AC SOlution

Above is the example of MLE v/s AC.

If anyone could tell me what I am mising...

Thanks in Advance.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

q.erase(q.begin()) in vector is O(n)

Edit: to be more specific, it is linear on the number of elements after the erased element, so it's O(1) if you erase from the end of the vector only.

set is O(log(n)) wherever the element is

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

For the second one (MLE) you are pushing repeated elements so it becomes exponential. With set that doesn't matter because a set has unique elements. Your vector solution passes if you sort and use unique to remove repeated elements. http://mirror.codeforces.com/contest/1072/submission/45192350

→ Ответить