結果

問題 No.945 YKC饅頭
ユーザー titiatitia
提出日時 2019-12-08 01:48:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,085 ms / 2,000 ms
コード長 2,737 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 126,296 KB
最終ジャッジ日時 2024-12-27 15:02:53
合計ジャッジ時間 30,409 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,480 KB
testcase_01 AC 46 ms
52,224 KB
testcase_02 AC 68 ms
66,304 KB
testcase_03 AC 82 ms
74,192 KB
testcase_04 AC 52 ms
60,800 KB
testcase_05 AC 86 ms
75,648 KB
testcase_06 AC 86 ms
75,776 KB
testcase_07 AC 82 ms
72,704 KB
testcase_08 AC 75 ms
63,616 KB
testcase_09 AC 77 ms
69,200 KB
testcase_10 AC 94 ms
75,904 KB
testcase_11 AC 72 ms
69,760 KB
testcase_12 AC 90 ms
76,160 KB
testcase_13 AC 89 ms
76,032 KB
testcase_14 AC 79 ms
73,984 KB
testcase_15 AC 52 ms
61,312 KB
testcase_16 AC 67 ms
67,328 KB
testcase_17 AC 72 ms
68,608 KB
testcase_18 AC 88 ms
73,216 KB
testcase_19 AC 77 ms
66,432 KB
testcase_20 AC 68 ms
64,384 KB
testcase_21 AC 60 ms
63,488 KB
testcase_22 AC 95 ms
75,904 KB
testcase_23 AC 103 ms
76,032 KB
testcase_24 AC 92 ms
76,160 KB
testcase_25 AC 104 ms
76,332 KB
testcase_26 AC 99 ms
75,648 KB
testcase_27 AC 70 ms
67,840 KB
testcase_28 AC 100 ms
72,448 KB
testcase_29 AC 43 ms
52,352 KB
testcase_30 AC 43 ms
51,968 KB
testcase_31 AC 247 ms
81,268 KB
testcase_32 AC 342 ms
81,184 KB
testcase_33 AC 542 ms
93,180 KB
testcase_34 AC 643 ms
103,380 KB
testcase_35 AC 937 ms
118,952 KB
testcase_36 AC 569 ms
110,208 KB
testcase_37 AC 567 ms
107,500 KB
testcase_38 AC 568 ms
104,644 KB
testcase_39 AC 344 ms
86,028 KB
testcase_40 AC 406 ms
89,192 KB
testcase_41 AC 279 ms
82,932 KB
testcase_42 AC 758 ms
114,084 KB
testcase_43 AC 462 ms
106,952 KB
testcase_44 AC 733 ms
111,232 KB
testcase_45 AC 801 ms
119,228 KB
testcase_46 AC 179 ms
81,704 KB
testcase_47 AC 615 ms
103,104 KB
testcase_48 AC 235 ms
83,236 KB
testcase_49 AC 395 ms
90,112 KB
testcase_50 AC 871 ms
120,604 KB
testcase_51 AC 1,040 ms
126,296 KB
testcase_52 AC 1,030 ms
125,740 KB
testcase_53 AC 1,073 ms
125,664 KB
testcase_54 AC 1,034 ms
125,048 KB
testcase_55 AC 1,085 ms
125,808 KB
testcase_56 AC 259 ms
86,120 KB
testcase_57 AC 389 ms
85,864 KB
testcase_58 AC 620 ms
112,480 KB
testcase_59 AC 696 ms
118,472 KB
testcase_60 AC 478 ms
96,672 KB
testcase_61 AC 642 ms
114,620 KB
testcase_62 AC 615 ms
112,856 KB
testcase_63 AC 421 ms
86,016 KB
testcase_64 AC 487 ms
98,104 KB
testcase_65 AC 635 ms
95,820 KB
testcase_66 AC 474 ms
94,596 KB
testcase_67 AC 555 ms
105,732 KB
testcase_68 AC 485 ms
97,432 KB
testcase_69 AC 431 ms
89,832 KB
testcase_70 AC 442 ms
90,700 KB
testcase_71 AC 450 ms
91,060 KB
testcase_72 AC 523 ms
101,852 KB
testcase_73 AC 682 ms
116,924 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