#1026706 (PyPy3) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	titia
提出日時	2024-11-15 08:39:17
言語	PyPy3 (7.3.15)
結果	MLE
実行時間	-
コード長	2,874 bytes
コンパイル時間	300 ms
コンパイル使用メモリ	82,304 KB
実行使用メモリ	319,812 KB
最終ジャッジ日時	2024-11-15 08:39:46
合計ジャッジ時間	26,984 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	49 ms 60,928 KB
testcase_01	AC	46 ms 60,612 KB
testcase_02	AC	54 ms 61,568 KB
testcase_03	AC	50 ms 62,208 KB
testcase_04	AC	50 ms 61,440 KB
testcase_05	AC	48 ms 61,440 KB
testcase_06	AC	47 ms 60,672 KB
testcase_07	AC	48 ms 61,360 KB
testcase_08	AC	49 ms 61,568 KB
testcase_09	AC	48 ms 61,060 KB
testcase_10	AC	47 ms 61,040 KB
testcase_11	AC	49 ms 61,184 KB
testcase_12	AC	50 ms 61,952 KB
testcase_13	AC	50 ms 61,568 KB
testcase_14	AC	48 ms 61,436 KB
testcase_15	AC	48 ms 61,384 KB
testcase_16	AC	48 ms 61,680 KB
testcase_17	AC	48 ms 61,952 KB
testcase_18	AC	48 ms 60,928 KB
testcase_19	AC	49 ms 61,952 KB
testcase_20	AC	47 ms 61,312 KB
testcase_21	AC	56 ms 61,440 KB
testcase_22	AC	91 ms 76,992 KB
testcase_23	AC	80 ms 78,372 KB
testcase_24	AC	95 ms 78,864 KB
testcase_25	AC	70 ms 73,216 KB
testcase_26	AC	102 ms 79,416 KB
testcase_27	AC	85 ms 78,900 KB
testcase_28	AC	82 ms 76,844 KB
testcase_29	AC	60 ms 66,688 KB
testcase_30	AC	72 ms 72,704 KB
testcase_31	AC	102 ms 78,992 KB
testcase_32	AC	196 ms 128,112 KB
testcase_33	AC	231 ms 104,576 KB
testcase_34	AC	298 ms 148,220 KB
testcase_35	AC	241 ms 132,852 KB
testcase_36	AC	211 ms 80,604 KB
testcase_37	AC	201 ms 124,888 KB
testcase_38	AC	167 ms 115,796 KB
testcase_39	AC	420 ms 152,884 KB
testcase_40	AC	242 ms 100,284 KB
testcase_41	AC	239 ms 121,148 KB
testcase_42	AC	305 ms 147,564 KB
testcase_43	AC	332 ms 123,520 KB
testcase_44	AC	337 ms 141,680 KB
testcase_45	AC	373 ms 89,300 KB
testcase_46	AC	408 ms 140,608 KB
testcase_47	AC	226 ms 111,872 KB
testcase_48	AC	262 ms 146,688 KB
testcase_49	AC	262 ms 147,712 KB
testcase_50	AC	174 ms 124,724 KB
testcase_51	AC	406 ms 144,256 KB
testcase_52	AC	290 ms 106,240 KB
testcase_53	AC	216 ms 105,344 KB
testcase_54	AC	285 ms 111,616 KB
testcase_55	AC	171 ms 105,984 KB
testcase_56	AC	169 ms 107,264 KB
testcase_57	AC	211 ms 101,248 KB
testcase_58	AC	372 ms 87,424 KB
testcase_59	AC	164 ms 97,920 KB
testcase_60	AC	247 ms 101,376 KB
testcase_61	AC	178 ms 81,784 KB
testcase_62	AC	270 ms 97,536 KB
testcase_63	AC	217 ms 99,200 KB
testcase_64	AC	174 ms 86,400 KB
testcase_65	AC	233 ms 138,216 KB
testcase_66	AC	212 ms 92,948 KB
testcase_67	AC	246 ms 115,876 KB
testcase_68	AC	258 ms 93,952 KB
testcase_69	AC	204 ms 152,840 KB
testcase_70	AC	172 ms 101,120 KB
testcase_71	AC	179 ms 103,168 KB
testcase_72	AC	274 ms 81,024 KB
testcase_73	AC	194 ms 126,036 KB
testcase_74	AC	291 ms 136,704 KB
testcase_75	AC	229 ms 103,628 KB
testcase_76	AC	225 ms 123,016 KB
testcase_77	AC	240 ms 145,664 KB
testcase_78	AC	350 ms 95,872 KB
testcase_79	AC	279 ms 117,616 KB
testcase_80	AC	262 ms 119,096 KB
testcase_81	AC	214 ms 121,344 KB
testcase_82	MLE	-
testcase_83	MLE	-
testcase_84	MLE	-
testcase_85	MLE	-
testcase_86	MLE	-
testcase_87	MLE	-
testcase_88	MLE	-
testcase_89	MLE	-
testcase_90	MLE	-
testcase_91	MLE	-
testcase_92	MLE	-
testcase_93	MLE	-

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

ソースコード

raw source code

import sys
input = sys.stdin.readline

class Bit_indexed_tree():
    def __init__(self, LEN):
        self.BIT = [0]*(LEN+1) # 1-indexedなtree. 配列BITの長さはLEN+1にしていることに注意。
        self.LEN = LEN

    def update(self,v,w): # index vにwを加える
        while v<=self.LEN:
            self.BIT[v]+=w
            v+=(v&(-v)) # v&(-v)で、最も下の立っているビット. 自分を含む大きなノードへ. たとえばv=3→v=4

    def getvalue(self,v): # [1,v]の区間の和を求める
        ANS=0
        while v!=0:
            ANS+=self.BIT[v]
            v-=(v&(-v)) # 自分より小さい自分の和を構成するノードへ. たとえばv=14→v=12へ
        return ANS

    def bisect_on_BIT(self,x): # [1,ind]の和がはじめてx以上になるindexを探す

        if x<=0:
            return 0
        
        ANS=0
        h=1<<((self.LEN).bit_length()-1) # LEN以下の最小の2ベキ
        while h>0:
            if ANS+h<=self.LEN and self.BIT[ANS+h]<x:
                x-=self.BIT[ANS+h]
                ANS+=h
            h//=2

        return ANS+1 # LENまでの和がx未満のとき, LEN+1を返すことに注意


# 線形篩。エラトステネスの篩を線形にできる。

MAX=2010
Sieve=[-1]*MAX
Primes=[]

for i in range(2,MAX):
    if Sieve[i]==-1:
        Primes.append(i)
        Sieve[i]=i

    for p in Primes:
        if p*i>=MAX or p>Sieve[i]:
            break
        else:
            Sieve[p*i]=p


# 素因数分解
def fact(x):
    D=dict()
    while x!=1:
        k=Sieve[x]
        if k in D:
            D[k]+=1
        else:
            D[k]=1
        x//=k
    return D

# 約数列挙
def faclist(x):
    LIST=[1]
    while x!=1:
        k=Sieve[x]
        count=0
        while x%k==0:
            count+=1
            x//=k

        LIST2=[]
        for l in LIST:
            for i in range(1,count+1):
                LIST2.append(l*k**i)
        LIST+=LIST2

    return LIST

N=int(input())
A=list(map(int,input().split()))

D=[-1]*2030
for i in range(len(Primes)):
    D[Primes[i]]=i

LIST=[Bit_indexed_tree(N+10) for i in range(305)]

for i in range(N):
    if A[i]==0:
        LIST[304].update(i+2,1)
        continue
    F=fact(A[i])

    for f in F:
        LIST[D[f]].update(i+2,F[f])

Q=int(input())

for tests in range(Q):
    p,l,r=map(int,input().split())

    k=LIST[304].getvalue(r-1+2)-LIST[304].getvalue(l-2+2)
    if k>0:
        print("Yes")
        continue
    if p==1:
        print("Yes")
        continue

    for i in range(304):
        if p%Primes[i]==0:
            k=LIST[i].getvalue(r-1+2)-LIST[i].getvalue(l-2+2)

            for tt in range(k):
                if p%Primes[i]==0:
                    p//=Primes[i]
                else:
                    break

    if p==1:
        print("Yes")
    else:
        print("NO")

yukicoder

結果

テストケース

ソースコード