結果

問題 No.945 YKC饅頭
ユーザー 👑 rin204rin204
提出日時 2022-02-11 21:11:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 885 ms / 2,000 ms
コード長 1,773 bytes
コンパイル時間 1,589 ms
コンパイル使用メモリ 86,604 KB
実行使用メモリ 135,012 KB
最終ジャッジ日時 2023-09-09 23:59:09
合計ジャッジ時間 29,611 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
70,972 KB
testcase_01 AC 76 ms
71,188 KB
testcase_02 AC 86 ms
75,448 KB
testcase_03 AC 122 ms
77,652 KB
testcase_04 AC 84 ms
75,356 KB
testcase_05 AC 91 ms
75,524 KB
testcase_06 AC 103 ms
75,660 KB
testcase_07 AC 97 ms
75,912 KB
testcase_08 AC 79 ms
71,336 KB
testcase_09 AC 97 ms
75,920 KB
testcase_10 AC 101 ms
75,768 KB
testcase_11 AC 92 ms
75,784 KB
testcase_12 AC 96 ms
76,084 KB
testcase_13 AC 113 ms
77,468 KB
testcase_14 AC 114 ms
77,456 KB
testcase_15 AC 96 ms
75,836 KB
testcase_16 AC 86 ms
75,408 KB
testcase_17 AC 118 ms
77,120 KB
testcase_18 AC 102 ms
75,980 KB
testcase_19 AC 78 ms
71,480 KB
testcase_20 AC 86 ms
75,684 KB
testcase_21 AC 90 ms
75,840 KB
testcase_22 AC 124 ms
77,528 KB
testcase_23 AC 122 ms
77,504 KB
testcase_24 AC 121 ms
77,360 KB
testcase_25 AC 124 ms
77,420 KB
testcase_26 AC 120 ms
77,480 KB
testcase_27 AC 76 ms
71,176 KB
testcase_28 AC 77 ms
71,188 KB
testcase_29 AC 74 ms
71,332 KB
testcase_30 AC 75 ms
71,168 KB
testcase_31 AC 216 ms
84,480 KB
testcase_32 AC 170 ms
87,780 KB
testcase_33 AC 362 ms
98,120 KB
testcase_34 AC 496 ms
105,916 KB
testcase_35 AC 736 ms
127,004 KB
testcase_36 AC 527 ms
105,184 KB
testcase_37 AC 488 ms
102,432 KB
testcase_38 AC 470 ms
101,652 KB
testcase_39 AC 297 ms
91,664 KB
testcase_40 AC 273 ms
93,068 KB
testcase_41 AC 193 ms
87,152 KB
testcase_42 AC 668 ms
114,120 KB
testcase_43 AC 458 ms
100,976 KB
testcase_44 AC 566 ms
114,424 KB
testcase_45 AC 675 ms
118,392 KB
testcase_46 AC 162 ms
84,260 KB
testcase_47 AC 488 ms
106,696 KB
testcase_48 AC 254 ms
84,168 KB
testcase_49 AC 342 ms
95,452 KB
testcase_50 AC 695 ms
119,836 KB
testcase_51 AC 805 ms
133,308 KB
testcase_52 AC 819 ms
133,620 KB
testcase_53 AC 797 ms
133,560 KB
testcase_54 AC 831 ms
135,012 KB
testcase_55 AC 814 ms
134,872 KB
testcase_56 AC 118 ms
90,980 KB
testcase_57 AC 118 ms
90,816 KB
testcase_58 AC 786 ms
115,284 KB
testcase_59 AC 870 ms
118,324 KB
testcase_60 AC 562 ms
105,404 KB
testcase_61 AC 752 ms
115,016 KB
testcase_62 AC 885 ms
116,380 KB
testcase_63 AC 146 ms
91,988 KB
testcase_64 AC 733 ms
107,600 KB
testcase_65 AC 574 ms
103,652 KB
testcase_66 AC 551 ms
103,424 KB
testcase_67 AC 636 ms
109,784 KB
testcase_68 AC 741 ms
108,628 KB
testcase_69 AC 304 ms
97,100 KB
testcase_70 AC 375 ms
97,820 KB
testcase_71 AC 362 ms
98,224 KB
testcase_72 AC 770 ms
110,568 KB
testcase_73 AC 845 ms
117,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

class Heapq:
    def __init__(self, lst = [], reverse = False):
        if reverse:
            self.pm = -1
            self.hq = [-l for l in lst]
        else:
            self.pm = 1
            self.hq = lst.copy()
        heapq.heapify(self.hq)
        self.tot = sum(lst)
        self.rm = []
        self.length = len(lst)
    
    def __bool__(self):
        return self.length > 0
        
    def __len__(self):
        return self.length
    
    def __getitem__(self, i):
        if i == 0:
            return self.top()
        else:
            assert False
            
    
    def push(self, x):
        self.length += 1
        heapq.heappush(self.hq, x * self.pm)
        self.tot += x
    
    def pop(self):
        self.length -= 1
        ret = heapq.heappop(self.hq)
        self.tot -= self.pm * ret
        self.delete()
        return self.pm * ret
    
    def top(self):
        return self.pm * self.hq[0]
    
    def remove(self, x): # 存在しないものを消そうとするとバグる
        self.length -= 1
        self.tot -= x
        heapq.heappush(self.rm, self.pm * x)
        self.delete()
            
    def delete(self):
        while self.rm and self.rm[0] == self.hq[0]:
            heapq.heappop(self.rm)
            heapq.heappop(self.hq)

n, m = map(int, input().split())
add = [[] for _ in range(n)]
rem = [[] for _ in range(n)]
T = [""] * m
for i in range(m):
    l, r, t = input().split()
    T[i] = t
    add[int(l) - 1].append(i)
    rem[int(r) - 1].append(i)
    
ans = {"Y":0, "K":0, "C":0}
hq = Heapq()
for i in range(n):
    for j in add[i]:
        hq.push(j)
    if hq:
        t = T[hq[0]]
        ans[t] += 1
    for j in rem[i]:
        hq.remove(j)

print(ans["Y"], ans["K"], ans["C"])
0