Блог пользователя Leftist_G

Автор Leftist_G, история, 6 дней назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 дней назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

  • »
    »
    5 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ^_^