#932547 (PyPy3) No.945 YKC饅頭

提出ソース

結果

問題	No.945 YKC饅頭
ユーザー	vwxyz
提出日時	2023-11-30 00:12:53
言語	PyPy3 (7.3.15)
結果	AC
実行時間	870 ms / 2,000 ms
コード長	4,110 bytes
コンパイル時間	354 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	133,812 KB
最終ジャッジ日時	2023-11-30 00:13:30
合計ジャッジ時間	36,417 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	125 ms 88,560 KB
testcase_01	AC	125 ms 88,560 KB
testcase_02	AC	144 ms 89,200 KB
testcase_03	AC	161 ms 89,456 KB
testcase_04	AC	139 ms 89,072 KB
testcase_05	AC	154 ms 89,200 KB
testcase_06	AC	183 ms 89,584 KB
testcase_07	AC	149 ms 89,200 KB
testcase_08	AC	142 ms 89,072 KB
testcase_09	AC	149 ms 89,200 KB
testcase_10	AC	151 ms 89,584 KB
testcase_11	AC	146 ms 89,200 KB
testcase_12	AC	154 ms 89,456 KB
testcase_13	AC	152 ms 89,456 KB
testcase_14	AC	181 ms 89,584 KB
testcase_15	AC	141 ms 89,072 KB
testcase_16	AC	140 ms 89,072 KB
testcase_17	AC	150 ms 89,584 KB
testcase_18	AC	155 ms 89,456 KB
testcase_19	AC	140 ms 89,072 KB
testcase_20	AC	148 ms 89,072 KB
testcase_21	AC	169 ms 89,200 KB
testcase_22	AC	166 ms 89,456 KB
testcase_23	AC	164 ms 89,584 KB
testcase_24	AC	161 ms 89,456 KB
testcase_25	AC	164 ms 90,096 KB
testcase_26	AC	160 ms 89,584 KB
testcase_27	AC	144 ms 89,072 KB
testcase_28	AC	170 ms 89,072 KB
testcase_29	AC	136 ms 88,560 KB
testcase_30	AC	142 ms 88,560 KB
testcase_31	AC	243 ms 93,016 KB
testcase_32	AC	283 ms 94,832 KB
testcase_33	AC	405 ms 101,744 KB
testcase_34	AC	496 ms 113,084 KB
testcase_35	AC	742 ms 127,312 KB
testcase_36	AC	500 ms 121,584 KB
testcase_37	AC	466 ms 117,156 KB
testcase_38	AC	511 ms 114,916 KB
testcase_39	AC	299 ms 97,564 KB
testcase_40	AC	343 ms 97,552 KB
testcase_41	AC	272 ms 94,780 KB
testcase_42	AC	656 ms 123,744 KB
testcase_43	AC	405 ms 118,168 KB
testcase_44	AC	606 ms 118,584 KB
testcase_45	AC	687 ms 128,776 KB
testcase_46	AC	229 ms 93,168 KB
testcase_47	AC	531 ms 113,532 KB
testcase_48	AC	248 ms 95,548 KB
testcase_49	AC	389 ms 101,488 KB
testcase_50	AC	692 ms 130,436 KB
testcase_51	AC	869 ms 133,808 KB
testcase_52	AC	870 ms 133,812 KB
testcase_53	AC	826 ms 133,764 KB
testcase_54	AC	824 ms 133,812 KB
testcase_55	AC	846 ms 133,756 KB
testcase_56	AC	286 ms 96,244 KB
testcase_57	AC	284 ms 96,244 KB
testcase_58	AC	649 ms 121,104 KB
testcase_59	AC	760 ms 126,368 KB
testcase_60	AC	459 ms 107,788 KB
testcase_61	AC	657 ms 123,024 KB
testcase_62	AC	665 ms 121,492 KB
testcase_63	AC	320 ms 97,188 KB
testcase_64	AC	471 ms 108,016 KB
testcase_65	AC	440 ms 105,992 KB
testcase_66	AC	455 ms 105,608 KB
testcase_67	AC	558 ms 114,424 KB
testcase_68	AC	463 ms 108,400 KB
testcase_69	AC	388 ms 99,364 KB
testcase_70	AC	408 ms 100,260 KB
testcase_71	AC	378 ms 100,388 KB
testcase_72	AC	507 ms 111,116 KB
testcase_73	AC	696 ms 124,960 KB

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

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
#sys.set_int_max_str_digits(10**9)

class Dual_Segment_Tree:
    def __init__(self,N,f_act,e_act,operate,lst):
        self.N=N
        self.f_act=f_act
        self.e_act=e_act
        self.operate=operate
        self.lst=[None]*self.N
        for i,x in enumerate(lst):
            self.lst[i]=x
        self.segment_tree_act=[self.e_act]*(self.N+self.N)

    def __getitem__(self,i):
        if type(i) is int:
            if -self.N<=i<0:
                i+=self.N*2
            elif 0<=i<self.N:
                i+=self.N
            else:
                raise IndexError("list index out of range")
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None or a<-self.N:
                a=0
            elif self.N<=a:
                a=self.N
            elif a<0:
                a+=self.N
            if b==None or self.N<=b:
                b=self.N
            elif b<-self.N:
                b=0
            elif b<0:
                b+=self.N
            return self.lst[slice(a,b,c)]

    def Operate_At(self,i):
        return self.operate(self.lst[i-self.N],self.segment_tree_act[i])

    def Propagate_At(self,i):
        self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
        self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
        self.segment_tree_act[i]=self.e_act

    def Propagate_Above(self,i):
        H=i.bit_length()-1
        for h in range(H,0,-1):
            self.Propagate_At(i>>h)

    def Operate_Range(self,a,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        L0=L//(L&-L)
        R0=R//(R&-R)-1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L<R:
            if L&1:
                self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
                L+=1
            if R&1:
                R-=1
                self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
            L>>=1
            R>>=1

    def Update(self):
        for i in range(1,self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i]=self.e_act

    def __str__(self):
        import copy
        segment_tree_act=copy.deepcopy(self.segment_tree_act)
        for i in range(1,self.N):
            segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
            segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
            segment_tree_act[i]=self.e_act
        return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(self.lst,segment_tree_act[self.N:])]))+"]"

N,M=map(int,readline().split())
LRT=[]
for m in range(M):
    l,r,t=readline().split()
    l=int(l)-1
    r=int(r)
    LRT.append((l,r,t))
def f_act(a,b):
    if b==None:
        return a
    return b
e_act=None
def operate(x,a):
    if a==None:
        return x
    return a
DST=Dual_Segment_Tree(N,f_act,e_act,operate,[None]*N)
for l,r,t in LRT[::-1]:
    DST.Operate_Range(t,l,r)
C=defaultdict(int)
for i in range(N):
    C[DST[i]]+=1
ans_lst=[C[s] for s in "YKC"]
print(*ans_lst)

yukicoder

結果

テストケース

ソースコード