#932547 (PyPy3) No.945 YKC饅頭

提出ソース

結果

問題	No.945 YKC饅頭
ユーザー	vwxyz
提出日時	2023-11-30 00:12:53
言語	PyPy3 (7.3.15)
結果	AC
実行時間	810 ms / 2,000 ms
コード長	4,110 bytes
コンパイル時間	208 ms
コンパイル使用メモリ	82,648 KB
実行使用メモリ	134,656 KB
最終ジャッジ日時	2024-09-26 13:46:08
合計ジャッジ時間	29,817 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	131 ms 89,344 KB
testcase_01	AC	125 ms 89,600 KB
testcase_02	AC	140 ms 90,112 KB
testcase_03	AC	160 ms 90,624 KB
testcase_04	AC	136 ms 90,112 KB
testcase_05	AC	148 ms 90,000 KB
testcase_06	AC	159 ms 90,252 KB
testcase_07	AC	151 ms 90,240 KB
testcase_08	AC	141 ms 89,728 KB
testcase_09	AC	147 ms 89,944 KB
testcase_10	AC	156 ms 90,732 KB
testcase_11	AC	149 ms 90,240 KB
testcase_12	AC	157 ms 90,168 KB
testcase_13	AC	156 ms 90,624 KB
testcase_14	AC	162 ms 90,496 KB
testcase_15	AC	144 ms 89,676 KB
testcase_16	AC	146 ms 90,112 KB
testcase_17	AC	163 ms 90,496 KB
testcase_18	AC	156 ms 90,496 KB
testcase_19	AC	146 ms 90,012 KB
testcase_20	AC	148 ms 90,112 KB
testcase_21	AC	146 ms 90,320 KB
testcase_22	AC	158 ms 90,496 KB
testcase_23	AC	166 ms 90,496 KB
testcase_24	AC	161 ms 90,528 KB
testcase_25	AC	165 ms 91,136 KB
testcase_26	AC	161 ms 90,624 KB
testcase_27	AC	144 ms 90,208 KB
testcase_28	AC	145 ms 89,856 KB
testcase_29	AC	129 ms 89,492 KB
testcase_30	AC	140 ms 89,236 KB
testcase_31	AC	220 ms 93,572 KB
testcase_32	AC	279 ms 95,744 KB
testcase_33	AC	374 ms 102,736 KB
testcase_34	AC	471 ms 113,928 KB
testcase_35	AC	685 ms 128,236 KB
testcase_36	AC	474 ms 122,164 KB
testcase_37	AC	448 ms 117,600 KB
testcase_38	AC	479 ms 115,592 KB
testcase_39	AC	300 ms 98,280 KB
testcase_40	AC	341 ms 98,280 KB
testcase_41	AC	263 ms 95,484 KB
testcase_42	AC	603 ms 124,544 KB
testcase_43	AC	393 ms 119,016 KB
testcase_44	AC	581 ms 119,112 KB
testcase_45	AC	623 ms 129,580 KB
testcase_46	AC	223 ms 94,204 KB
testcase_47	AC	494 ms 114,564 KB
testcase_48	AC	237 ms 96,256 KB
testcase_49	AC	345 ms 102,008 KB
testcase_50	AC	674 ms 131,356 KB
testcase_51	AC	804 ms 134,224 KB
testcase_52	AC	810 ms 134,604 KB
testcase_53	AC	808 ms 134,656 KB
testcase_54	AC	802 ms 134,656 KB
testcase_55	AC	804 ms 134,604 KB
testcase_56	AC	286 ms 97,408 KB
testcase_57	AC	277 ms 97,152 KB
testcase_58	AC	625 ms 122,780 KB
testcase_59	AC	682 ms 128,284 KB
testcase_60	AC	438 ms 108,544 KB
testcase_61	AC	636 ms 124,948 KB
testcase_62	AC	622 ms 123,552 KB
testcase_63	AC	319 ms 98,176 KB
testcase_64	AC	456 ms 108,808 KB
testcase_65	AC	433 ms 106,920 KB
testcase_66	AC	432 ms 106,496 KB
testcase_67	AC	555 ms 115,308 KB
testcase_68	AC	448 ms 109,312 KB
testcase_69	AC	358 ms 99,484 KB
testcase_70	AC	365 ms 100,840 KB
testcase_71	AC	370 ms 100,784 KB
testcase_72	AC	494 ms 112,016 KB
testcase_73	AC	663 ms 126,396 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

結果

テストケース

ソースコード