On this problem before accessing an element in a map checking if the element is contained or not makes program faster. It doesnt make sense to me. Isnt both log(n) comp? Or is there an exception on accessing elements which are not in container?
TLE: 10498148
AC: 10498342
I only changed that part between these.
Also can someone tell how to use unordered map or give a code using it? Or any type of hashmap implementation i can use in c++.
UPD: It looks like when you use [] operator you create a node so tree size grows each time. Thanks for help everybody.
It happens because
operator[]actually inserts element into map if it was not found. Therefore, your map grows during execution. You can clearly see this by looking at memory consumption.Reasoning is very simple: otherwise you won't be able to write code like
a[x] = b;.operator[]is unable to determine what you're gonna do with the result — just check or write something. So, it always returns reference to an element and, therefore, this element has to be created.Operator [] inserts (key,0) into the map if the key wasn't there, so the size of the map grows and subsequent requests will take more time.
If you use
m.find(val), then it only looks up whethervalis contained in the existing tree. If you usem[val], then it first creates a new tree node, initializes it with a default value and then returns it to you. So naturallym[val]is more expensive both in time and space.