結果
| 問題 | No.854 公平なりんご分配 |
| ユーザー |
 titia
|
| 提出日時 | 2024-11-15 08:22:02 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,820 bytes |
| コンパイル時間 | 556 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 326,668 KB |
| 最終ジャッジ日時 | 2024-11-15 08:25:44 |
| 合計ジャッジ時間 | 202,473 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 54 ms
66,304 KB |
| testcase_01 | AC | 52 ms
67,976 KB |
| testcase_02 | AC | 51 ms
66,688 KB |
| testcase_03 | AC | 49 ms
69,020 KB |
| testcase_04 | AC | 49 ms
66,560 KB |
| testcase_05 | AC | 56 ms
69,828 KB |
| testcase_06 | AC | 47 ms
66,816 KB |
| testcase_07 | AC | 48 ms
68,108 KB |
| testcase_08 | AC | 50 ms
67,072 KB |
| testcase_09 | AC | 48 ms
69,232 KB |
| testcase_10 | AC | 48 ms
66,432 KB |
| testcase_11 | AC | 49 ms
69,476 KB |
| testcase_12 | AC | 50 ms
67,072 KB |
| testcase_13 | AC | 49 ms
70,696 KB |
| testcase_14 | AC | 48 ms
66,816 KB |
| testcase_15 | AC | 50 ms
69,736 KB |
| testcase_16 | AC | 48 ms
66,816 KB |
| testcase_17 | AC | 50 ms
68,776 KB |
| testcase_18 | AC | 47 ms
66,432 KB |
| testcase_19 | AC | 48 ms
70,724 KB |
| testcase_20 | AC | 55 ms
66,432 KB |
| testcase_21 | AC | 50 ms
70,240 KB |
| testcase_22 | AC | 92 ms
82,816 KB |
| testcase_23 | AC | 87 ms
85,336 KB |
| testcase_24 | AC | 107 ms
84,932 KB |
| testcase_25 | AC | 74 ms
81,016 KB |
| testcase_26 | AC | 105 ms
85,080 KB |
| testcase_27 | AC | 90 ms
86,028 KB |
| testcase_28 | AC | 84 ms
83,200 KB |
| testcase_29 | AC | 61 ms
75,396 KB |
| testcase_30 | AC | 73 ms
79,488 KB |
| testcase_31 | AC | 103 ms
86,064 KB |
| testcase_32 | AC | 416 ms
133,888 KB |
| testcase_33 | AC | 600 ms
111,952 KB |
| testcase_34 | AC | 1,584 ms
154,256 KB |
| testcase_35 | AC | 898 ms
140,096 KB |
| testcase_36 | AC | 289 ms
86,588 KB |
| testcase_37 | AC | 388 ms
132,272 KB |
| testcase_38 | AC | 267 ms
121,344 KB |
| testcase_39 | AC | 2,911 ms
159,972 KB |
| testcase_40 | AC | 680 ms
105,984 KB |
| testcase_41 | AC | 915 ms
128,492 KB |
| testcase_42 | AC | 1,220 ms
153,216 KB |
| testcase_43 | AC | 1,722 ms
131,032 KB |
| testcase_44 | AC | 1,973 ms
147,640 KB |
| testcase_45 | AC | 901 ms
96,472 KB |
| testcase_46 | AC | 2,831 ms
146,488 KB |
| testcase_47 | AC | 589 ms
119,292 KB |
| testcase_48 | AC | 1,044 ms
151,808 KB |
| testcase_49 | AC | 880 ms
154,928 KB |
| testcase_50 | AC | 294 ms
129,860 KB |
| testcase_51 | AC | 2,862 ms
151,872 KB |
| testcase_52 | TLE | - |
| testcase_53 | TLE | - |
| testcase_54 | TLE | - |
| testcase_55 | TLE | - |
| testcase_56 | TLE | - |
| testcase_57 | TLE | - |
| testcase_58 | TLE | - |
| testcase_59 | TLE | - |
| testcase_60 | MLE | - |
| testcase_61 | MLE | - |
| testcase_62 | MLE | - |
| testcase_63 | MLE | - |
| testcase_64 | MLE | - |
| testcase_65 | MLE | - |
| testcase_66 | MLE | - |
| testcase_67 | MLE | - |
| testcase_68 | MLE | - |
| testcase_69 | MLE | - |
| testcase_70 | MLE | - |
| testcase_71 | MLE | - |
| testcase_72 | MLE | - |
| testcase_73 | MLE | - |
| testcase_74 | MLE | - |
| testcase_75 | MLE | - |
| testcase_76 | MLE | - |
| testcase_77 | MLE | - |
| testcase_78 | MLE | - |
| testcase_79 | MLE | - |
| testcase_80 | TLE | - |
| testcase_81 | TLE | - |
| testcase_82 | TLE | - |
| testcase_83 | TLE | - |
| testcase_84 | MLE | - |
| testcase_85 | TLE | - |
| testcase_86 | TLE | - |
| testcase_87 | TLE | - |
| testcase_88 | TLE | - |
| testcase_89 | TLE | - |
| testcase_90 | TLE | - |
| testcase_91 | TLE | - |
| testcase_92 | TLE | - |
| testcase_93 | MLE | - |
ソースコード
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)
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("NO")
continue
if p==1:
print("Yes")
continue
flag=1
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]
if p==1:
print("Yes")
else:
print("NO")