結果

問題 No.1705 Mode of long array
ユーザー puzneko
提出日時 2021-10-30 00:51:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 570 ms / 3,000 ms
コード長 1,927 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 200,320 KB
最終ジャッジ日時 2024-10-07 13:15:45
合計ジャッジ時間 21,741 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin
import heapq
d = dict()

class HeapDict:
    def __init__(self):
        self.h=[]
        self.d=dict()

    def insert(self,x):
        heapq.heappush(self.h,x)
        if x not in self.d:
            self.d[x]=1
        else:
            self.d[x]+=1

    def erase(self,x):
        if x not in self.d or self.d[x]==0:
            print(x,"is not in HeapDict")
            exit()
        else:
            self.d[x]-=1

        while len(self.h)!=0:
            if self.d[self.h[0]]==0:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self,x):
        if x in self.d and self.d[x]!=0:
            return True
        else:
            return False

    def is_empty(self):
        if self.h:
            return False
        else:
            return True

    def get_min(self):
        return self.h[0]

n, m, *indata = map(int, stdin.read().split())
numlist = [0 for i in range(m+1)]
numset = HeapDict()
for i in range(m):
    a = indata[i]
    numlist[i+1] = a
    if not (numset.is_exist(-a)):
        d[-a] = HeapDict()
    d[-a].insert(-i-1)
    numset.insert(-a)

q = indata[m]

offset = m+1
for i in range(q):
    t, x, y  = indata[offset + 3*i],indata[offset + 3*i+1],indata[offset + 3*i+2]
    if t == 1:
        kari = numlist[x]
        d[-kari].erase(-x)
        numset.erase(-kari)
        kari += y
        numlist[x] += y
        if not (numset.is_exist(-kari)):
            d[-kari] = HeapDict()
        numset.insert(-kari)
        d[-kari].insert(-x)
    elif t == 2:
        kari = numlist[x]
        d[-kari].erase(-x)
        numset.erase(-kari)
        kari -= y
        numlist[x] -= y
        if not (numset.is_exist(-kari)):
            d[-kari] = HeapDict()
        numset.insert(-kari)
        d[-kari].insert(-x)
    else:
        maxnum = numset.get_min()
        ans = - d[maxnum].get_min()
        print("{}".format(ans))
0