I got MLE in this submission. After investigation it turned out that I created empty containers before a recursive call (in the get_delete_x_ans function), resulting in creation of many such containers when call stack is deep.
That sounds reasonable, but when I did the calculation, it seemed impossible that this mistake could lead to MLE when the mem limit is 512MB.
So the calculation goes:
My later accepted solution uses 175100KB, limit is ~524288KB, difference is 300000+KB = approx. 300MB.
So it means that the submission above created empty containers that take up 300MB space.
It will create 2 empty queue, each is 48 byte on a 64-bit machine.
Recursion depth is <=500000 from problem description. So total space of empty containers is 2 x 48B x 500000 = approx. 5x10^7 B = 50MB.
That's much less than 300MB, so if the calculation was correct, I shouldn't get MLE.
Can someone help point out what's wrong with my calculation above? Thanks!
Auto comment: topic has been updated by Sigh (previous revision, new revision, compare).
An empty
queue(to be precise, an emptydeque) allocates much more memory by default.Compare 272637612 and 272637639, where the only difference is having an 100000-sized array of empty
queues. This took 68700 more KB, so we can assume each queue took around 0.687 KB. I don't get where that 48 came from, but evensizeof(q)whereqis aqueue<int>shows 80 in custom invocation (C++20), but in reality the dynamically allocated part is not reflected in it. It costs far more than that.