For problem E, this code, implemented using unordered_map, was giving MLE. So, I switched to 2D array. However, now this is giving TLE. Isn't 2D array faster than unordered_map? How is it giving TLE when the former isn't? Is it because of any UB?
Time complexity: O(n * k + total_t_len + q * k)
Space complexity: n* k * 4 bytes = 1000000 * 26 * 4 ≈ 100MB (fits comfortably in 512MB)
I think that the unordered_map IS giving you TLE but it doesn't show cuz the memory limit exceeded
it is pretty unusual for unordered_map to give mle as it takes less space than 2d array ,although you can try 2d array declared globally because if you redeclare a huge array in every testcase it takes a time overhead which may cause tle,i faced similar issue few days back although in my case unordered_map worked as the array was sparse .and another point is you used Big O notation . it is to understand the timecomplexity in terms of polynomial like n^2 is greater than nlogn or n something like that.the real time usage in the program will fall on the BIG O mention family but the seconds may be different in measuring actual time,say you are redeclaring a 2D array in every test case will consume more clock ticks than the the case you declare it globally