結果

問題 No.945 YKC饅頭
ユーザー titiatitia
提出日時 2019-12-08 01:48:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,069 ms / 2,000 ms
コード長 2,737 bytes
コンパイル時間 1,283 ms
コンパイル使用メモリ 86,972 KB
実行使用メモリ 127,168 KB
最終ジャッジ日時 2023-08-27 14:59:30
合計ジャッジ時間 32,024 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
70,912 KB
testcase_01 AC 68 ms
70,908 KB
testcase_02 AC 89 ms
75,980 KB
testcase_03 AC 100 ms
76,760 KB
testcase_04 AC 77 ms
75,408 KB
testcase_05 AC 100 ms
76,864 KB
testcase_06 AC 101 ms
77,180 KB
testcase_07 AC 98 ms
76,904 KB
testcase_08 AC 79 ms
75,716 KB
testcase_09 AC 91 ms
75,828 KB
testcase_10 AC 102 ms
76,860 KB
testcase_11 AC 94 ms
75,976 KB
testcase_12 AC 114 ms
77,096 KB
testcase_13 AC 106 ms
76,788 KB
testcase_14 AC 102 ms
76,620 KB
testcase_15 AC 78 ms
75,800 KB
testcase_16 AC 91 ms
76,124 KB
testcase_17 AC 94 ms
75,836 KB
testcase_18 AC 103 ms
76,668 KB
testcase_19 AC 91 ms
75,756 KB
testcase_20 AC 83 ms
75,840 KB
testcase_21 AC 83 ms
75,936 KB
testcase_22 AC 105 ms
77,292 KB
testcase_23 AC 112 ms
77,228 KB
testcase_24 AC 107 ms
76,648 KB
testcase_25 AC 111 ms
76,940 KB
testcase_26 AC 110 ms
77,004 KB
testcase_27 AC 90 ms
76,056 KB
testcase_28 AC 96 ms
76,804 KB
testcase_29 AC 69 ms
70,780 KB
testcase_30 AC 67 ms
71,192 KB
testcase_31 AC 240 ms
82,540 KB
testcase_32 AC 316 ms
82,856 KB
testcase_33 AC 496 ms
94,496 KB
testcase_34 AC 548 ms
105,468 KB
testcase_35 AC 882 ms
120,488 KB
testcase_36 AC 548 ms
111,604 KB
testcase_37 AC 560 ms
109,512 KB
testcase_38 AC 563 ms
106,176 KB
testcase_39 AC 343 ms
87,788 KB
testcase_40 AC 411 ms
91,972 KB
testcase_41 AC 295 ms
83,708 KB
testcase_42 AC 714 ms
114,836 KB
testcase_43 AC 460 ms
108,348 KB
testcase_44 AC 724 ms
112,348 KB
testcase_45 AC 785 ms
120,764 KB
testcase_46 AC 196 ms
82,652 KB
testcase_47 AC 618 ms
105,044 KB
testcase_48 AC 237 ms
84,396 KB
testcase_49 AC 404 ms
91,760 KB
testcase_50 AC 858 ms
122,264 KB
testcase_51 AC 1,000 ms
126,656 KB
testcase_52 AC 980 ms
126,776 KB
testcase_53 AC 1,046 ms
127,168 KB
testcase_54 AC 1,013 ms
126,788 KB
testcase_55 AC 1,069 ms
127,100 KB
testcase_56 AC 265 ms
86,756 KB
testcase_57 AC 419 ms
86,712 KB
testcase_58 AC 630 ms
113,388 KB
testcase_59 AC 682 ms
119,400 KB
testcase_60 AC 486 ms
98,616 KB
testcase_61 AC 611 ms
115,344 KB
testcase_62 AC 620 ms
114,752 KB
testcase_63 AC 429 ms
87,280 KB
testcase_64 AC 482 ms
99,960 KB
testcase_65 AC 479 ms
97,596 KB
testcase_66 AC 477 ms
96,976 KB
testcase_67 AC 562 ms
106,808 KB
testcase_68 AC 500 ms
98,928 KB
testcase_69 AC 452 ms
90,780 KB
testcase_70 AC 455 ms
91,340 KB
testcase_71 AC 463 ms
91,536 KB
testcase_72 AC 545 ms
102,920 KB
testcase_73 AC 665 ms
117,624 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,M=map(int,input().split())

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
seg_height=1+N.bit_length() # Segment treeの高さ
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[None]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R): # 遅延伝搬すべきノードのリストを返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=None:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=LAZY[ind]
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=None

    while L!=R:
        if L > R:
            SEG[L]=x * (1<<(seg_height - (L.bit_length())))
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x * (1<<(seg_height - (R.bit_length())))
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=SEG[ind<<1]+SEG[1+(ind<<1)]

def getvalues(l,r): # 区間[l,r)に関する和を調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=None:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=LAZY[ind]
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=None
            
    ANS=0

    while L!=R:
        if L > R:
            ANS+=SEG[L]
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS+=SEG[R]
            R//=(R & (-R))

    return ANS

QLIST=[list(input().split()) for i in range(M)]

for L,R,T in QLIST[::-1]:
    L=int(L)
    R=int(R)
    if T=="Y":
        updates(L,R+1,1)
    elif T=="K":
        updates(L,R+1,2)
    else:
        updates(L,R+1,3)

ANSY=0
ANSK=0
ANSC=0

for i in range(1,N+1):
    #print(getvalues(i,i+1))
    if getvalues(i,i+1)==1:
        ANSY+=1
    elif getvalues(i,i+1)==2:
        ANSK+=1
    elif getvalues(i,i+1)==3:
        ANSC+=1

print(ANSY,ANSK,ANSC)
0