Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3496 |

3 | apiadu | 3438 |

4 | TLE | 3356 |

5 | LHiC | 3339 |

6 | mnbvmar | 3281 |

7 | 300iq | 3267 |

8 | Radewoosh | 3242 |

9 | yosupo | 3233 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

4 | vovuh | 168 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 154 |

10 | rng_58 | 153 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2020 16:11:04 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Operations on std::map are

GUARANTEEDO(logn) while on std::unordered_map areAVERAGEO(1) which means with map you get always O(logn) and with unordered_map you may get sometimes O(n) in worst case.unordered_map worst case usually happens when the hash function is producing collisions for every insertion in the map.

Another approach could be using binary search the answer. The problem is similar to sliding window problem. Start with binary searching length of the interval then check whether u are able to find a sliding window with atmost k distict elements or not. If yes then store the L,R of the interval.GOOD LUCK:)

http://codeforces.com/blog/entry/62393

Unordered map is implemented with Hash Table, that is the reason why it's performance relies on the hash function, the average time is O(1), but worst case O(n). While map is implemented with self-balancing red-black tree, and operations are O(log n) always. That is why it is giving u TLE with map and not with unordered map, but there are times when it is the other way around, checking this blog might help u :) https://codeforces.com/blog/entry/21853