Earlier today I was writing a dynamic segment tree for the problem 915-E

My solution gave Memory Limit Exceeded Verdict. Then I made a small change in my code, surprisingly it got accepted.

Submission with MLE:-

node* create()
{
	node *tmp=new node;
	// Some more lines to initialize the variables
	return tmp;
}

Accepted Submission:-

node ns[15000000];
int cnt=0;

node* create()
{
	node *tmp=&ns[cnt++];
	// Some more lines to initialize the variables
	return tmp;
}

I was very confused I had no idea why it worked. I even added the assertion assert(cnt < 15000000) and it still passed. I do not understand why my second solution is consuming less memory. It probably has something to do with how dynamic memory allocation works. Can anyone explain?

Here is the full code:

• MLE solution
• Accepted solution