Recently, I have tried a problem: 1893B - Neutral Tonality and solved it with O(NlogN) tc.

Problem Summary: Insert array b into array a at any position while making sure that the LIS is minized.

Approach: For an element el of the array a insert the elements of b which are greater than or equal to el.

However, the solution got TLE on the third test case: Submission 282567664

What's wrong in my approach/code? Can anyone help me to debug this problem?

Code: Used multiset to find elements and map to store the elements.

void solve()
{
    int n, m, x;
    cin >> n >> m;

    vi a(n);
    multiset<int> ms;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> x, ms.insert(x);

    map<int, vi> elements;
    forr(i, 0, n - 1)
    {
        auto it = lb(a[i], ms);
        while (it != ms.end())
        {
            elements[i].pb(*it);
            ms.erase(it);
            if (!sz(ms))
                break;
            it = lb(a[i], ms);
        }
    }

    forr(i, 0, n - 1)
    {
        reverse(all(elements[i]));
        for (int v : elements[i])
            printsp(v);
        printsp(a[i]);
    }

    while (sz(ms))
        printsp(*ms.rbegin()), ms.erase(--ms.end());
}

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);

Hello everyone,

Today, I attempted a problem having 6 seconds time limit. This problem has n and q values which need to be taken care of before selecting the expected solution which ultimately will fit into the constraints.

On this problem, as mentioned we need to consider the number of queries in each test case. Please read the full problem for better understanding: Problem Link

Key constraints: The sum of q over all test cases does not exceed 10^5, and the sum of n over all test cases does not exceed 10^5.

So, if I run a nested loop of n inside the loop of q then the time complexity would be O(q*n) that means (10^5)*(10^5) which is 10^10. The problem has a 6 seconds time limit. But my solution gave TLE. My Submission

Where do I have to optimize and how can I calculate such a complex scenario where the time limit is more than 1 second and have to consider the number of queries also (basically q value)?

Additional Question: if within 1 second, the 10^8 operation is executable then how many operations can I execute within 6 seconds?

Thanks in advance:)