SQRSUBMA June Lunchtime How to resolve TLE?

Approach: https://youtu.be/AtIhmHEyGrY?t=2194

It is correct for 50 points but TLE for 100 points.

Can anybody tell why is it TLE?

Problem Link: https://www.codechef.com/LTIME85B/problems/SQRSUBMA

My Submission: https://www.codechef.com/viewsolution/34864039

Ideone Link: https://ideone.com/ZtKgZ6

Update: AC Submission 100 Points

Don’t use maps use a frequency array instead

Have You Tried unordered_map instead of map?

@zephxr Yes.
Unordered Map Submission
Still TLE

I think array can work instead of map and once try printf scanf instead cin cout.

@zephxr No help either from scanf printf

@cubefreak777 If X=10^6 then side length can be 10^5 as 10^5 is factor of X. And if all array elements are 10^6 . Then sum would be 10^6*10^5=10^11. This value won’t fit in freq array.

You only have to consider sums that are less than X , so you can have a frequency array of size 1e6

1 Like

Have you tried using array?

@zephxr @cubefreak777 Yes I tried
But why was any kind of map giving me TLE?
AC Submission 100 Points

1 Like

Map takes O(Logn) time in worst case
Unordered map takes O(1) time in best case and O(n) Time in Worst case
Array takes O(1) time in worst case.

1 Like