Hello coders,

I've recently encountered a perplexing issue while working on a problem where the input size (N) is up to 200,000. Despite my algorithm's O( n log n ) complexity, it consistently hits a Time Limit Exceeded (TLE) error on the 8th test case. I've optimized my code to the best of my ability and ensured it's running in O(NlogN) time complexity, but the problem persists. Can anyone help me to debug this problem?

Problem: 1955D - Inaccurate Subsequence Search

Submission: 267829049

Additional: I managed to solve this problem by replacing the multiset. Here is my second submission: 267810516. But I'm very much curious about why the n log n solution didn't work. Did I miscalculate the time complexity or miss something crucial?

Main Code of first submission: Iterate over n and log n for counting element in multiset

    int cnt = 0;
    map<int, int> mpp;
    for (int i = 0; i < m; i++)
    {
        mpp[a[i]]++;
        if (ms.count(a[i]) >= mpp[a[i]])
            cnt++;
    }
 
    int ans = cnt >= k;
    for (int i = 0; i < n - m; i++)
    {
        mpp[a[i]]--;
        if (ms.count(a[i]) > mpp[a[i]])
            cnt--;
 
        mpp[a[i + m]]++;
        if (ms.count(a[i + m]) >= mpp[a[i + m]])
            cnt++;
        ans += cnt >= k;
    }
 
    print(ans);