TLE with unordered_map

Правка en3, от shanto_bangladesh, 2022-05-15 14:46:30

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; }

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!

Теги data structures, time complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский shanto_bangladesh 2022-05-16 17:39:54 71
en4 Английский shanto_bangladesh 2022-05-15 14:47:09 2 Tiny change: '\nCode: \n~~~~~\nv' -> '\nCode: \n\n~~~~~\nv'
en3 Английский shanto_bangladesh 2022-05-15 14:46:30 49 (published)
en2 Английский shanto_bangladesh 2022-05-15 14:44:36 1161
en1 Английский shanto_bangladesh 2022-05-15 14:39:18 72 Initial revision (saved to drafts)