Can anyone please help me find error in my code
https://www.codechef.com/viewsolution/34894482
@ganesh_6 , @udayan14
You are using a map. It will give TLE with map . Use frequency arrays. Look at my solution above for reference.
your optimisation is similar to setter’s code can you please give quick explanation
Use prefix sum to quickly calculate sums in sliding windows. Use a frequency array and set it to zero initially. For each possible value of square side, first fill the frequrncy array, then instead of iterating over the frequency array to count, we iterate over the array A( See the addition to output variable in the second for loop, there’s no multiplication in there). Finally, we only set those elements to 0 in the frequency array which are modified. We don’t each element to 0 (as most elements are already 0). Doing these optimizations will help you get AC. Ask if you need any more clarification.
map in c++ sort the elements according to keys in ascending order. This will cost log(n) in the worst case. Try using an array for storing the frequencies of elements. Refer editorial. You will get a better insights. Your logic is right. The only thing is that use freq array or unordered_map