pickle_juice2024's blog

By pickle_juice2024, history, 9 months ago, In English

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
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But I already have this:

    if (cnt < maxx - minn + 1) {
        cout << 0 << "\n";
        return;
    }
    

    This means that maxx — minn + 1 is at most cnt, which in turn is at most 2e5?