提出 #32048295

---

ソースコード 拡げる

import bisect
from collections import defaultdict

# 順序付きSet(insertの使い分けによって重複有り/無しの使い分け可能)
class MultiSet:
    def __init__(self):
        self.total = 0  # Multi_setに含まれる要素数
        self.ms = dict()  # 各要素の個数カウント用
        self.lr = []  # 要素の重複を排除した昇順リスト(一度追加されたものはdelete処理の後も残る)

    # 重複を許さない挿入
    def insert_unique(self, x):
        if x in self.ms:
            if self.ms[x] == 0:
                self.ms[x] = 1
                self.total += 1
        else:
            self.total += 1
            self.ms[x] = 1
            bisect.insort(self.lr, x)

    # 重複を許す挿入
    def insert_multi(self, x):
        self.total += 1
        if x in self.ms:
            self.ms[x] += 1
        else:
            self.ms[x] = 1
            bisect.insort(self.lr, x)

    # 要素の存在判定(有り:1、無し:0をReturn)
    def find(self, x):
        return self.ms.get(x, 0)

    # 要素の削除(重複を許している場合は値がxの要素を全て削除)
    def delete(self, x):
        if self.find(x) > 0:
            self.total -= self.ms[x]
            self.ms[x] = 0
            del self.lr[self.lr.index(x)]

    def delete_num(self, x, num):
        if self.find(x) > 0:
            if num >= self.ms[x]:
                self.delete(x)
            else:
                self.total -= num
                self.ms[x] -= num

    def max_value(self):
        return self.lr[-1]

    def min_value(self):
        return self.lr[0]

    # 値がl以上r以下の要素を抽出したリストをReturn
    def dump(self, l, r):
        lb = bisect.bisect_left(self.lr, l)
        ub = bisect.bisect_right(self.lr, r)
        res = []
        for i in range(lb, ub):
            k = self.lr[i]
            v = self.ms[k]
            res += [k] * v
        return res


"""
MS = MultiSet()
MS.insert_unique(x)
MS.insert_multi(x)
MS.find(x)
MS.delete(x)
MS.dump(l,r) # [l,r)
"""
MS = MultiSet()
count = defaultdict(int)


Q = int(input())
for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        MS.insert_multi(query[1])
        count[query[1]] += 1
    elif query[0] == 2:
        x = query[1]
        num = query[2]
        MS.delete_num(x, num)
    else:
        print(MS.max_value() - MS.min_value())

提出情報

ジャッジ結果