Using unordered map with custom hash mentioned below for storing frquency/kind of prefix sum but gives TLE and using map gets accepted.
For the first time I have seen unordered map with this custom hash is getting TLE because of it.
(Custom hash from blog )
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
void solve()
{
long long n;cin>>n;
long long a[n];f(n)cin>>a[i];
unordered_map<long long,long long,custom_hash>lp;
lp[0]++;
long long s=0;long long ans=0;
f(n){
s+=a[i];
if(lp[s]>0){ans++;s=0;lp.clear();lp[0]++;}
else lp[s]++;
}cout<<ans<<endl;
}
Can anyone please explain it
It's literally explained so well in the blog you linked. Why do you want the explanation again?
In blog, Its saying that using custom hash with unordered map is fine and can be restricted by getting tle and it worked for me untill above mentioned code gave Tle to unordered map with cutsom hash while gp_hash_table with custom hash and map is getting accepted.
That's the confusion in my mind that why i want some clarifications
lp.clear()is a O(N) operation. You code essentially runs into O(N^2) in worst case.