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

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

I was recently trying to solve problem K. Kingdom of Ants on Kattis. However, my submission strangely receives a Memory Limit Exceeded verdict, and I can see no way of achieving that with my code.

Code: https://pastebin.com/0sXQaCdi

Do you guys spot any reasons why the above code would give MLE? Maybe some weird C++ undefined behaviour, or maybe some compiler flaw?

UPDATE: After checking for the (very degenerate) case if there is only one y-coordinate (right between lines 119 and 120), the solution gets Accepted verdict. However, I still don't understand why the initial verdict was MLE, and it was very misleading.

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

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

Auto comment: topic has been updated by bicsi (previous revision, new revision, compare).

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

I think the bug is in initializing the segment tree. It looks like the right bound is initially set to n-2 instead of n-1. The way the init function is defined, this recurses forever instead of RTEing.

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

    You are right. I posted this before I realized that there can be degenerate rectangles in the input tests. Stack overflow is indeed a reasonable cause of a MLE verdict. I marked the issue as closed.