This is regarding the Chef and Xor queries problem which came in Dec challenge. I am getting TLE in two test cases of last test cases. Link to the solution. I have used square root decomposition and tried to lazily make the updates as and when required. But no luck yet.

The timeout was caused by the use of operator[] when fetching the map value.

When you try to access a mapped value through operator[], it allocates the element (i.e. mapped value for searched key) if not already present. So, it allocates unnecessary elements in the map, resulting in slower search operation.

I got your solution accepted for 100 points by checking if the key is allocated a value in the map or not, before accessing the map through this condition :

if(dp[i].find(xorNeed) != dp[i].end()) 

Edited code :


1 Like