proAakash's blog

memory limit exceeded!! HOW?
By proAakash, history, 3 hours ago, In English

problem:- https://mirror.codeforces.com/contest/1996/problem/C

I was solving the above problem using C++ vector of maps and i got memory limit exceeded. But I solved the same problem with the same logic using vectors of vector and got accepted solution .I am unable to understand why the solution using maps failed.

Solution using maps:- https://mirror.codeforces.com/contest/1996/submission/273021146

Solution using vectors of vector:- https://mirror.codeforces.com/contest/1996/submission/273020910

Can someone expalin?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by proAakash (previous revision, new revision, compare).

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by proAakash (previous revision, new revision, compare).

→ Reply
»
2 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Vector needs to store only the value for each element

Map needs to store key, value, color, pointers to left son, right son and parent for each element (and maybe even more, I am not sure)

So it's just usual MLE, map needs much more memory

→ Reply