Sorry, not being acquainted with STL quite that well. I somehow assumed map is akin to a hash map, but later came to know insertion takes O(logn) as it keeps the objects in sorted order, which is not needed for my code.I also saw somewhere the mention of a hash_map/unordered_map and supposedly it has been included in the TR1, but I wasn't able to use it.
Anyway, this time, I took each side in two arrays, sorted one of them and looked up each element of the other in this, appropriately increasing count as we go.
Also since there might be more than one match in the sorted array for any particular element, I had to use while loops to count all the matches on either side of the match returned by a binary search.
Things did not go well though, as it successfully TLE'd this time as well
Is it because I used STL's implementation of sort and bsearch ?
Here is the code