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]-— 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!↵
↵
↵
↵
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]
{↵
if(r
{↵
r = g[i-1]; ↵
l = cl; ↵
}↵
↵
cl = g[i]; ↵
}↵
}↵
↵
if(g[n-1]
{↵
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!↵
↵
↵