собес 2, но нормальный код
#include <bits/stdc++.h>


class Data {
public:
  Data() {}

  void inc(const std::string& key) {
    int counter = stringToCounter[key];

    auto it = counterToIterator.find(counter + 1);
    auto prevIterator = counterToIterator.find(counter);

    std::list<std::pair<int, std::unordered_set<std::string>>>::iterator itNext, itPrev;

    if (it != counterToIterator.end()) {
      itNext = it->second;
    }

    if (prevIterator != counterToIterator.end()) {
      itPrev = prevIterator->second;
    }


    if (counter > 0) {
      removeStringFromBucket(key, prevIterator->second);
    }

    if (it == counterToIterator.end()) {
      if (prevIterator == counterToIterator.end()) {
        std::unordered_set<std::string> set;
        itNext = data.emplace(data.begin(), counter + 1, set);
        counterToIterator.emplace(counter + 1, itNext);
      } else {
        std::unordered_set<std::string> set;
        itNext = data.emplace(std::next(prevIterator->second), counter + 1, set);
        counterToIterator.emplace(counter + 1, itNext);
      }
    }

    stringToCounter[key]++;
    addStringToBucket(key, itNext);
  }

  void dec(const std::string& key) {
    auto itCounter = stringToCounter.find(key);

    if (itCounter == stringToCounter.end()) {
      return;
    }

    int counter = itCounter->second;
    itCounter->second--;

    auto it = counterToIterator.find(counter - 1);
    auto prevIterator = counterToIterator.find(counter);

    std::list<std::pair<int, std::unordered_set<std::string>>>::iterator itNext, itPrev;

    if (it != counterToIterator.end()) {
      itNext = it->second;
    }

    if (prevIterator != counterToIterator.end()) {
      itPrev = prevIterator->second;
    }

    if (counter == 1) {
      stringToCounter.erase(key);
      removeStringFromBucket(key, itPrev);
      return;
    }

    if (it == counterToIterator.end()) {
      std::unordered_set<std::string> set;
      itNext = data.emplace(itPrev, counter - 1, set);
      counterToIterator.emplace(counter - 1, itNext);
    }

    removeStringFromBucket(key, itPrev);
    addStringToBucket(key, itNext);
  }

  std::string getMaxKey() const {
    if (data.size() == 0) {
      throw "No elements in Data";
    }

    auto it = data.rbegin();

    return *((it->second).begin());
  }

  std::string getMinKey() const {
    if (data.size() == 0) {
      throw "No elements in Data";
    }

    auto it = data.begin();

    return *((it->second).begin());
  }

  bool check(std::map<std::string, int> mp) {
    for (auto& [s, cnt] : stringToCounter) {
      if (mp[s] != cnt) {
        std::cout << s << ' ' << cnt << ' ' << mp[s] << std::endl;
        return false;
      }
      if (cnt == 0) return false;
    }
    return true;
  }

private:

  void removeStringFromBucket(const std::string& key, std::list<std::pair<int, std::unordered_set<std::string>>>::iterator it) {
    (it->second).erase(key);
    if ((it->second).size() == 0) {
      counterToIterator.erase(it->first);
      data.erase(it);
    }
  }

  void addStringToBucket(const std::string& key, std::list<std::pair<int, std::unordered_set<std::string>>>::iterator it) {
    (it->second).insert(key);
  }

  std::list<std::pair<int, std::unordered_set<std::string>>> data;
  std::unordered_map<std::string, int> stringToCounter;
  std::unordered_map<int, std::list<std::pair<int, std::unordered_set<std::string>>>::iterator> counterToIterator;

};


int main() {
  Data data;
  std::map<std::string, int> mp;


  for (int i = 0; i < 100000000; i++) {
    std::string cur = std::to_string(rand() % 1000);
    int t = rand() & 1;
    if (t) {
      data.inc(cur);
      mp[cur]++;
    } else {
      data.dec(cur);
      if (mp[cur] > 0) mp[cur]--;
    }

    if (i % 100000 == 0) {
      std::cout << i << ' ' << "OK" << std::endl;
    }
  }

}