Advertisement
Guest User

Untitled

a guest
Feb 19th, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #define MAXN 200000
  2.  
  3. class AllOne {
  4. public:
  5.     unordered_map<string, int> mp;
  6.     unordered_set<string> strings_cnt[MAXN];
  7.     int mn, mx;
  8.     /** Initialize your data structure here. */
  9.     AllOne() {
  10.         mn = mx = 0;
  11.     }
  12.    
  13.     /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
  14.     void inc(string key) {
  15.         int prev;
  16.         if (mp.find(key) == mp.end()) {
  17.             mp[key] = 1;
  18.             prev = 0;
  19.         }
  20.         else {
  21.             prev = mp[key];
  22.             mp[key]++;
  23.         }
  24.         if (prev != 0) {
  25.             strings_cnt[prev].erase(key);
  26.         }
  27.         strings_cnt[prev + 1].insert(key);
  28.  
  29.         if (strings_cnt[mn].size() == 0)
  30.             mn++;
  31.         if (mx == prev)
  32.             mx++;
  33.         if (prev == 0)
  34.             mn = 1;
  35.     }
  36.    
  37.     /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
  38.     void dec(string key) {
  39.        
  40.         if (mp.find(key) == mp.end())
  41.             return;
  42.         int prev = mp[key];
  43.         if (prev == 1)
  44.             mp.erase(key);
  45.         else
  46.             mp[key]--;
  47.         strings_cnt[prev].erase(key);
  48.         if (prev > 1)
  49.             strings_cnt[prev - 1].insert(key);
  50.        
  51.         if (strings_cnt[mx].size() == 0)
  52.             mx--;
  53.        
  54.         if (mn == prev) {
  55.             mn--;
  56.             if (mn == 0 && mx > 0) {
  57.                 for (int i = 1; i <= mx; i++)
  58.                     if (strings_cnt[i].size() > 0) {
  59.                         mn = i;
  60.                         break;
  61.                     }
  62.             }
  63.         }
  64.        
  65.     }
  66.    
  67.     /** Returns one of the keys with maximal value. */
  68.     string getMaxKey() {
  69.         if (strings_cnt[mx].size() == 0)
  70.             return "";
  71.         unordered_set<string>::iterator it = strings_cnt[mx].begin();
  72.         return *it;
  73.     }
  74.    
  75.     /** Returns one of the keys with Minimal value. */
  76.     string getMinKey() {
  77.         if (strings_cnt[mn].size() == 0)
  78.             return "";
  79.         unordered_set<string>::iterator it = strings_cnt[mn].begin();
  80.         return *it;
  81.     }
  82. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement