TLE with unordered_map
Difference between en2 and en3, changed 49 character(s)
In  last Div. 4 contest, my solution for problem [Problem F](https://codeforces.com/contest/1676/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; }↵


sort(g.begin(), g.end()); ↵

int l = 0, r = -1, cl = g[0]; ↵
  n = g.size(); ↵
  for(int i = 1; i<n; i++)↵
  {↵
      if(g[i] 
-&mdash; g[i-1]>1)↵
      {↵
        if(r 
-&mdash; l <= g[i-1] -&mdash; cl)↵
        {↵
          r = g[i-1]; ↵
          l = cl; ↵
        }↵

        cl = g[i]; ↵
      }↵
  }↵

 if(g[n-1] 
-&mdash; cl >= r -&mdash; 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!↵


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)