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]
[1]: https://www.codechef.com/viewsolution/16576761
1 Like