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

Автор pickle_juice2024, история, 8 месяцев назад, По-английски

I am currently solving 1893C: https://mirror.codeforces.com/contest/1893/problem/C.
For some strange reason my code gives MLE when the space complexity of my code is O(n + m) (at least I think so?). If anyone could help me, it would be highly appreciated. My code:

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

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

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

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Fixed the MLE, here's your TLE!

Submission: https://mirror.codeforces.com/contest/1893/submission/251179543

You iterate from minn to maxx but the maximum value of maxx-minn is very big.

Spoiler

The reason for the MLE is that when iterating from minn to maxx and iterating through the elements of m[i] even if there was no element added to m[i] it will initialize to an empty vector. A simple check if m[i] exists fixes this.

Edit: I also fixed the TLE: https://mirror.codeforces.com/contest/1893/submission/251180328.