TLE with unordered_map

Revision en5, by shanto_bangladesh, 2022-05-16 17:39:54

In last Div. 4 contest, my solution for problem Problem F received TLE verdict in testcase 18 during the system test. Later on I found that, changing unordered_map to map works fine to achieve Accepted verdict.

Code:

void solve()
{   
 
int n, k; cin >> n >> k ; 
vi g; 
unordered_map<int, int> m; 
for(int i = 0; i<n; i++)
{
  int a; cin >> a; 
  m[a]++; 
}
 
for(auto &x: m)
{
  if(x.second>=k) 
  {
      g.pb(x.first); 
  }
}
 
if(g.size()==0) { cout << -1 << "\n"; return; }
 
 
Asort(g); 
 
int l = 0, r = -1, cl = g[0]; 
  n = g.size(); 
  for(int i = 1; i<n; i++)
  {
      if(g[i] - g[i-1]>1)
      {
        if(r - l <= g[i-1] - cl)
        {
          r = g[i-1]; 
          l = cl; 
        }
 
        cl = g[i]; 
      }
  }
 
 if(g[n-1] - cl >= r - l )
    {
      r = g[n-1]; l = cl; 
    }
 
    cout << l << " " << r << '\n'; 
 
}
 

So far I know, when we do not need the elements to be ordered, we should use unordered_map which is the case in this problem. So why std::map works better than std::unordered_map in terms of time complexity?

Thanks for your patience!

Tags data structures, time complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English shanto_bangladesh 2022-05-16 17:39:54 71
en4 English shanto_bangladesh 2022-05-15 14:47:09 2 Tiny change: '\nCode: \n~~~~~\nv' -> '\nCode: \n\n~~~~~\nv'
en3 English shanto_bangladesh 2022-05-15 14:46:30 49 (published)
en2 English shanto_bangladesh 2022-05-15 14:44:36 1161
en1 English shanto_bangladesh 2022-05-15 14:39:18 72 Initial revision (saved to drafts)