recursively's blog

Memory limit exceeded although using much less
By recursively, history, 5 years ago, In English

So, I'm trying to solve the Multiset problem (https://mirror.codeforces.com/contest/1354/problem/D).

The memory limit is:

but then I get a MLE although I'm only using 19MB (far from 28MB).

What's the rationale behind this?

My code only uses the following data:

        int n2 = 1048576;
        int[] actualArray = new int[2 * n2];

so it should be about (2 * 1048576) * 4 bytes ~= 8MB. So, again, I'm far from 19MB. Any ideas why I get MLE?

The idea of my algorithm (https://mirror.codeforces.com/contest/1354/submission/82629303) is to use a segment tree. Where every leaf correspond to values from 1 to 10^6 (maximum n) and a leaf i contains how many times a value i exists in the initial array. Then, we sum up the leaves, etc.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Majority of the input is in a single line. Taking it all in (which you do using readLine) uses high amount of memory.

You need to read partial parts of the line. I don't have enough experience in Java to tell you how, but I do remember that this problem was very hostile to Java programmers.

→ Reply