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?

#### History

Revisions

Rev. Lang. By When Δ Comment