#407735 (PyPy3) No.945 YKC饅頭

提出ソース

結果

問題	No.945 YKC饅頭
ユーザー	mkawa2
提出日時	2019-12-12 09:20:54
言語	PyPy3 (7.3.15)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	1,943 bytes
コンパイル時間	785 ms
コンパイル使用メモリ	87,100 KB
実行使用メモリ	135,016 KB
最終ジャッジ日時	2023-09-07 00:08:47
合計ジャッジ時間	48,306 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	87 ms 71,728 KB
testcase_01	AC	89 ms 71,860 KB
testcase_02	AC	123 ms 77,280 KB
testcase_03	AC	131 ms 78,284 KB
testcase_04	AC	103 ms 76,976 KB
testcase_05	AC	118 ms 76,924 KB
testcase_06	AC	127 ms 77,544 KB
testcase_07	AC	150 ms 78,040 KB
testcase_08	AC	111 ms 76,904 KB
testcase_09	AC	155 ms 78,776 KB
testcase_10	AC	182 ms 79,124 KB
testcase_11	AC	143 ms 78,148 KB
testcase_12	AC	135 ms 77,868 KB
testcase_13	AC	131 ms 77,808 KB
testcase_14	AC	131 ms 77,744 KB
testcase_15	AC	123 ms 77,144 KB
testcase_16	AC	118 ms 77,328 KB
testcase_17	AC	131 ms 78,176 KB
testcase_18	AC	127 ms 77,544 KB
testcase_19	AC	96 ms 76,748 KB
testcase_20	AC	127 ms 77,168 KB
testcase_21	AC	124 ms 76,996 KB
testcase_22	AC	191 ms 79,424 KB
testcase_23	AC	134 ms 77,928 KB
testcase_24	AC	140 ms 78,292 KB
testcase_25	AC	145 ms 78,396 KB
testcase_26	AC	181 ms 79,148 KB
testcase_27	AC	92 ms 71,624 KB
testcase_28	AC	91 ms 71,768 KB
testcase_29	AC	89 ms 71,920 KB
testcase_30	AC	89 ms 71,856 KB
testcase_31	AC	240 ms 84,244 KB
testcase_32	AC	169 ms 84,708 KB
testcase_33	AC	551 ms 97,896 KB
testcase_34	AC	1,124 ms 108,628 KB
testcase_35	TLE	-
testcase_36	AC	1,300 ms 114,500 KB
testcase_37	AC	1,218 ms 111,524 KB
testcase_38	AC	1,231 ms 110,972 KB
testcase_39	AC	372 ms 89,668 KB
testcase_40	AC	336 ms 93,672 KB
testcase_41	AC	205 ms 85,816 KB
testcase_42	AC	1,642 ms 120,400 KB
testcase_43	AC	1,049 ms 111,592 KB
testcase_44	AC	1,321 ms 117,972 KB
testcase_45	AC	1,646 ms 125,764 KB
testcase_46	AC	157 ms 83,864 KB
testcase_47	AC	1,170 ms 107,728 KB
testcase_48	AC	311 ms 85,000 KB
testcase_49	AC	530 ms 94,268 KB
testcase_50	AC	1,688 ms 127,264 KB
testcase_51	TLE	-
testcase_52	AC	1,855 ms 134,552 KB
testcase_53	TLE	-
testcase_54	TLE	-
testcase_55	AC	1,903 ms 134,512 KB
testcase_56	AC	113 ms 89,080 KB
testcase_57	AC	112 ms 88,584 KB
testcase_58	AC	1,075 ms 120,112 KB
testcase_59	AC	1,278 ms 127,412 KB
testcase_60	AC	501 ms 102,220 KB
testcase_61	AC	1,157 ms 124,696 KB
testcase_62	AC	1,069 ms 122,820 KB
testcase_63	AC	194 ms 90,864 KB
testcase_64	AC	649 ms 105,388 KB
testcase_65	AC	498 ms 102,644 KB
testcase_66	AC	504 ms 101,984 KB
testcase_67	AC	845 ms 112,868 KB
testcase_68	AC	562 ms 104,432 KB
testcase_69	AC	309 ms 95,684 KB
testcase_70	AC	366 ms 95,540 KB
testcase_71	AC	319 ms 95,704 KB
testcase_72	AC	814 ms 110,260 KB
testcase_73	AC	1,209 ms 125,544 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class SegmentTree:
    def __init__(self, aa):
        width = 1 << ((len(aa) - 1).bit_length())
        tree = [-1] * (width * 2 - 1)
        lazy = [-1] * (width * 2 - 1)
        tree[width - 1:] = aa
        self.width = width
        self.tree = tree
        self.lazy = lazy

    def _prop(self, u):
        if self.lazy[u] == -1: return
        value = self.tree[u] = self.lazy[u]
        self.lazy[u] = -1
        if u < self.width - 1:
            self.lazy[u * 2 + 1] = self.lazy[u * 2 + 2] = value

    def update(self, l, r, a, u=0, uL=0, uR=-1):
        if uR == -1: uR = self.width
        self._prop(u)
        if r <= uL or uR <= l:
            return
        elif l <= uL and uR <= r:
            self.lazy[u] = a
            return
        uM = (uL + uR) // 2
        self.update(l, r, a, u * 2 + 1, uL, uM)
        self.update(l, r, a, u * 2 + 2, uM, uR)

    def get_elements(self):
        for u in range(self.width - 1):
            self._prop(u)
        for u in range(self.width - 1, self.width * 2 - 1):
            if self.lazy[u] == -1: continue
            self.tree[u] = self.lazy[u]
        return self.tree[self.width - 1:]

def main():
    n, m = MI()
    lrt = [input().split() for _ in range(m)]
    aa = [-1] * n
    st = SegmentTree(aa)
    for l, r, t in lrt[::-1]:
        l, r = int1(l), int(r)
        if t == "Y":
            mark = 1
        elif t == "K":
            mark = 2
        else:
            mark = 3
        st.update(l, r, mark)
    aa = st.get_elements()
    cnt = defaultdict(int)
    for a in aa:
        cnt[a] += 1
    print(cnt[1], cnt[2], cnt[3])

main()

yukicoder

結果

テストケース

ソースコード