Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define MAXN 200000
- class AllOne {
- public:
- unordered_map<string, int> mp;
- unordered_set<string> strings_cnt[MAXN];
- int mn, mx;
- /** Initialize your data structure here. */
- AllOne() {
- mn = mx = 0;
- }
- /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
- void inc(string key) {
- int prev;
- if (mp.find(key) == mp.end()) {
- mp[key] = 1;
- prev = 0;
- }
- else {
- prev = mp[key];
- mp[key]++;
- }
- if (prev != 0) {
- strings_cnt[prev].erase(key);
- }
- strings_cnt[prev + 1].insert(key);
- if (strings_cnt[mn].size() == 0)
- mn++;
- if (mx == prev)
- mx++;
- if (prev == 0)
- mn = 1;
- }
- /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
- void dec(string key) {
- if (mp.find(key) == mp.end())
- return;
- int prev = mp[key];
- if (prev == 1)
- mp.erase(key);
- else
- mp[key]--;
- strings_cnt[prev].erase(key);
- if (prev > 1)
- strings_cnt[prev - 1].insert(key);
- if (strings_cnt[mx].size() == 0)
- mx--;
- if (mn == prev) {
- mn--;
- if (mn == 0 && mx > 0) {
- for (int i = 1; i <= mx; i++)
- if (strings_cnt[i].size() > 0) {
- mn = i;
- break;
- }
- }
- }
- }
- /** Returns one of the keys with maximal value. */
- string getMaxKey() {
- if (strings_cnt[mx].size() == 0)
- return "";
- unordered_set<string>::iterator it = strings_cnt[mx].begin();
- return *it;
- }
- /** Returns one of the keys with Minimal value. */
- string getMinKey() {
- if (strings_cnt[mn].size() == 0)
- return "";
- unordered_set<string>::iterator it = strings_cnt[mn].begin();
- return *it;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement