topK

[Astral-23]

template <int n, typename K, typename T> struct tops_arbitary {
    struct D {
        K key;
        T val;
    };
    array<D, n> ar;
    array<bool, n> flg;

    bool add(const K &key, const T &val) {
        bool ret = false;
        bool found = false;
        for (int i = 0; i < n; i++)
            if (flg[i] == true) {
                if (ar[i].key == key) {
                    ret = chmin(ar[i].val, val);
                    found = true;
                }
            }

        if (found == false) {
            if (flg[n - 1] == false || ar[n - 1].val > val) {
                ar[n - 1] = {key, val};
                flg[n - 1] = true;
                ret = true;
            }
        }

        if (ret) {
            for (int i = n - 1; i >= 1; i--) if(flg[i]) {
                if (flg[i - 1] == false || ar[i - 1].val > ar[i].val) {
                    swap(ar[i], ar[i - 1]);
                    swap(flg[i], flg[i - 1]);
                } 
            }
        }
        return ret;
    }

    bool contains(const K &key, const T &val) {
        for (int i = 0; i < n; i++)
            if (flg[i]) {
                if (ar[i].key == key && ar[i].val == val) return true;
            }
        return false;
    }

    bool is_null(const T &ban_key) const {
        if (flg[0] == false) return true;
        if (ar[0].key == ban_key && flg[1] == false) return true;
        return false;
    }

    T operator()(const T &ban_key) const {
        if (ban_key == ar[0].key)
            return ar[1].val;
        else
            return ar[0].val;
    }

    int sz() const {
        int i = 0;
        for (; i < n; i++)
            if (flg[i] == false) break;
        return i;
    }

    bool empty() const { return !flg[0]; }
};

using tops = tops_arbitary<2, ll, ll>;

https://atcoder.jp/contests/abc245/submissions/59499740

[Astral-23]

add ... 追加されたらtrue, else false contains ... {key, val}が今のtop nに含まれているか is_null... ban_keyを除いた時、登録されている値が存在しないか