Unordered Map Mystery

Revision en1, by algoskipper, 2024-10-25 19:46:32

Question link

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

Tags unordered_map, map vs unordered_map

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English algoskipper 2024-10-25 19:46:32 1201 Initial revision (published)