結果

問題 No.1705 Mode of long array
ユーザー puznekopuzneko
提出日時 2021-10-30 00:51:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 605 ms / 3,000 ms
コード長 1,927 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 200,592 KB
最終ジャッジ日時 2024-04-16 16:06:02
合計ジャッジ時間 23,748 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,864 KB
testcase_01 AC 41 ms
53,248 KB
testcase_02 AC 41 ms
53,120 KB
testcase_03 AC 90 ms
76,928 KB
testcase_04 AC 77 ms
73,984 KB
testcase_05 AC 87 ms
76,932 KB
testcase_06 AC 156 ms
78,848 KB
testcase_07 AC 162 ms
80,512 KB
testcase_08 AC 168 ms
79,720 KB
testcase_09 AC 163 ms
78,968 KB
testcase_10 AC 156 ms
78,500 KB
testcase_11 AC 155 ms
79,232 KB
testcase_12 AC 156 ms
79,488 KB
testcase_13 AC 514 ms
184,944 KB
testcase_14 AC 363 ms
129,112 KB
testcase_15 AC 351 ms
121,600 KB
testcase_16 AC 421 ms
147,892 KB
testcase_17 AC 332 ms
116,240 KB
testcase_18 AC 292 ms
108,160 KB
testcase_19 AC 468 ms
163,356 KB
testcase_20 AC 334 ms
119,192 KB
testcase_21 AC 392 ms
140,464 KB
testcase_22 AC 569 ms
200,592 KB
testcase_23 AC 482 ms
131,584 KB
testcase_24 AC 464 ms
131,456 KB
testcase_25 AC 442 ms
131,456 KB
testcase_26 AC 433 ms
131,376 KB
testcase_27 AC 452 ms
131,688 KB
testcase_28 AC 408 ms
131,456 KB
testcase_29 AC 369 ms
131,756 KB
testcase_30 AC 414 ms
131,840 KB
testcase_31 AC 462 ms
131,712 KB
testcase_32 AC 376 ms
131,456 KB
testcase_33 AC 599 ms
187,620 KB
testcase_34 AC 597 ms
187,660 KB
testcase_35 AC 594 ms
186,860 KB
testcase_36 AC 605 ms
187,380 KB
testcase_37 AC 602 ms
188,144 KB
testcase_38 AC 599 ms
186,612 KB
testcase_39 AC 603 ms
187,112 KB
testcase_40 AC 602 ms
187,380 KB
testcase_41 AC 599 ms
186,980 KB
testcase_42 AC 602 ms
187,368 KB
testcase_43 AC 218 ms
138,836 KB
testcase_44 AC 236 ms
139,088 KB
testcase_45 AC 234 ms
138,960 KB
testcase_46 AC 223 ms
138,952 KB
testcase_47 AC 237 ms
138,800 KB
testcase_48 AC 237 ms
139,216 KB
testcase_49 AC 458 ms
146,968 KB
testcase_50 AC 452 ms
147,088 KB
testcase_51 AC 447 ms
147,096 KB
testcase_52 AC 455 ms
148,116 KB
testcase_53 AC 459 ms
146,328 KB
権限があれば一括ダウンロードができます

ソースコード

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