Leftist_G's blog

Why my 2053F with segment tree always MLE on test 4?
By Leftist_G, history, 3 days ago, In English

I solved this problem with segment tree, but when I submitted my solution, it told me "Memory limit exceeded on test 4". I calculated my static memory usage, it's far from 512MiB. So why?

My submission

Just now, I tried changing my solution to be the same as official solution (linear memory usage), and I got MLE again...

New submission

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

»
3 days ago, # |
  Vote: I like it +19 Vote: I do not like it

I copied your solution to custom invocation, and tried to simplify as much as possible without changing the verdict. Eventually, I realised: the culprit is

fr1(i,1,n-1){
    for(auto j:bol[i]) coef[i]+=1ll*j.se*bol[i+1][j.fi];
}

Here you essentially create quadratic memory by creating entries in the bol[i] for all numbers, that are present in any row from 1 to i-th — remember that even access to a std::map creates an entry. So, if n = 1e5, m = 1, and all numbers are distinct, than you create approximately n*n/2 entries in the maps.

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is really hard for me to find it... especially when I felt desperate because of the verdict in the contest. :(

    Anyway, thanks for your help! Appreciate ^_^

    → Reply