結果

問題 No.1705 Mode of long array
ユーザー puznekopuzneko
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,936 KB
testcase_01 AC 36 ms
53,556 KB
testcase_02 AC 37 ms
53,356 KB
testcase_03 AC 83 ms
76,652 KB
testcase_04 AC 69 ms
74,164 KB
testcase_05 AC 78 ms
76,232 KB
testcase_06 AC 139 ms
78,568 KB
testcase_07 AC 137 ms
80,052 KB
testcase_08 AC 143 ms
79,308 KB
testcase_09 AC 148 ms
79,060 KB
testcase_10 AC 133 ms
78,528 KB
testcase_11 AC 134 ms
78,916 KB
testcase_12 AC 137 ms
79,000 KB
testcase_13 AC 451 ms
184,688 KB
testcase_14 AC 327 ms
128,508 KB
testcase_15 AC 300 ms
121,064 KB
testcase_16 AC 364 ms
148,028 KB
testcase_17 AC 279 ms
116,280 KB
testcase_18 AC 253 ms
107,936 KB
testcase_19 AC 408 ms
162,960 KB
testcase_20 AC 288 ms
119,024 KB
testcase_21 AC 357 ms
140,624 KB
testcase_22 AC 504 ms
200,320 KB
testcase_23 AC 438 ms
131,428 KB
testcase_24 AC 417 ms
130,952 KB
testcase_25 AC 396 ms
131,376 KB
testcase_26 AC 382 ms
131,636 KB
testcase_27 AC 396 ms
131,572 KB
testcase_28 AC 358 ms
131,496 KB
testcase_29 AC 335 ms
131,248 KB
testcase_30 AC 363 ms
131,192 KB
testcase_31 AC 411 ms
131,368 KB
testcase_32 AC 347 ms
131,272 KB
testcase_33 AC 531 ms
187,056 KB
testcase_34 AC 528 ms
187,512 KB
testcase_35 AC 555 ms
186,416 KB
testcase_36 AC 565 ms
186,940 KB
testcase_37 AC 530 ms
187,764 KB
testcase_38 AC 534 ms
186,872 KB
testcase_39 AC 539 ms
186,704 KB
testcase_40 AC 550 ms
186,832 KB
testcase_41 AC 544 ms
186,676 KB
testcase_42 AC 570 ms
186,456 KB
testcase_43 AC 211 ms
138,884 KB
testcase_44 AC 221 ms
138,472 KB
testcase_45 AC 217 ms
138,896 KB
testcase_46 AC 211 ms
138,412 KB
testcase_47 AC 224 ms
138,412 KB
testcase_48 AC 228 ms
138,612 KB
testcase_49 AC 422 ms
146,964 KB
testcase_50 AC 419 ms
146,440 KB
testcase_51 AC 405 ms
146,964 KB
testcase_52 AC 415 ms
147,600 KB
testcase_53 AC 405 ms
146,452 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