Как оптимизировать этот простой алгоритм?

Примечание: это вызов программирования

Эта задача требует использования std::set.

Ввод

Число n
n строк с каждым j и k

Пример ввода:

j для операции: 1 для вставки k, 2 для удаления k (если есть k), 3 find k

Для j == 3 введите Yes или No, если k находится в std::set.

Я сделал разные версии алгоритма, но все они слишком медленные. Я пробовал разные функции std, но std::find кажется самым быстрым, но все еще слишком медленным. Реализация моего собственного будет еще хуже, поэтому, возможно, я пропустил функцию из библиотеки. Я действительно не знаю, как оптимизировать его дальше. В настоящее время у меня есть это:

int main()
{
    std::set<int> set{};
    int Q = 0;
    std::cin >> Q;

    int type = 0;
    int x = 0;
    for (int i = 0; i < Q; ++i)
    {
        std::cin >> type;
        std::cin >> x;

        if (type == 1)
            set.insert(x);
        else if (type == 2)
            set.erase(x);
        else if (type == 3)
            std::cout << (std::find(std::begin(set), std::end(set), x) != std::end(set) ? "Yes" : "No") << '\n';
            //Condition may be std::find, std::count or std::binary_search
    }

    return 0;
}

Задача требует, чтобы она работала менее 2 секунд. Вот мои результаты:

Function              Time           % over
std::find          -> 7.410s         370.50%
std::count         -> 7.881s         394.05%
std::binary_search -> 14.050s        702.50%

Как вы можете видеть, мой алгоритм в 3 раза медленнее, чем требуемый алгоритм. Узкие места, очевидно, являются такими функциями:

Function               % of total time 
std::find          ->  77.61%
std::count         ->  80.80%
std::binary_search ->  87.59%

Но в настоящее время у меня нет лучшей идеи, чем использовать std::find или подобные функции. У кого-то есть способ/идея, чтобы еще больше оптимизировать мой код? Или есть некоторые очевидные узкие места, которые мне не хватает?

Ответ 1