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

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	ああいい
提出日時	2022-03-04 19:05:34
言語	PyPy3 (7.3.15)
結果	MLE
実行時間	-
コード長	1,299 bytes
コンパイル時間	1,014 ms
コンパイル使用メモリ	87,128 KB
実行使用メモリ	329,740 KB
最終ジャッジ日時	2023-09-25 20:22:06
合計ジャッジ時間	46,233 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	76 ms 75,424 KB
testcase_01	AC	76 ms 75,472 KB
testcase_02	AC	76 ms 75,256 KB
testcase_03	AC	78 ms 75,736 KB
testcase_04	AC	76 ms 75,272 KB
testcase_05	AC	79 ms 75,600 KB
testcase_06	AC	80 ms 75,524 KB
testcase_07	AC	77 ms 75,524 KB
testcase_08	AC	77 ms 75,712 KB
testcase_09	AC	77 ms 75,708 KB
testcase_10	AC	77 ms 75,392 KB
testcase_11	AC	77 ms 75,672 KB
testcase_12	AC	81 ms 75,776 KB
testcase_13	AC	80 ms 75,812 KB
testcase_14	AC	76 ms 75,332 KB
testcase_15	AC	80 ms 75,604 KB
testcase_16	AC	81 ms 75,640 KB
testcase_17	AC	82 ms 75,592 KB
testcase_18	AC	79 ms 75,520 KB
testcase_19	AC	81 ms 75,696 KB
testcase_20	AC	80 ms 75,516 KB
testcase_21	AC	80 ms 75,500 KB
testcase_22	AC	123 ms 77,900 KB
testcase_23	AC	100 ms 76,340 KB
testcase_24	AC	132 ms 80,224 KB
testcase_25	AC	103 ms 77,204 KB
testcase_26	AC	135 ms 80,408 KB
testcase_27	AC	119 ms 79,684 KB
testcase_28	AC	117 ms 78,416 KB
testcase_29	AC	92 ms 75,896 KB
testcase_30	AC	98 ms 76,352 KB
testcase_31	AC	134 ms 80,204 KB
testcase_32	AC	367 ms 130,344 KB
testcase_33	AC	336 ms 105,612 KB
testcase_34	AC	547 ms 150,520 KB
testcase_35	AC	448 ms 134,476 KB
testcase_36	AC	257 ms 81,284 KB
testcase_37	AC	356 ms 127,172 KB
testcase_38	AC	305 ms 117,264 KB
testcase_39	AC	715 ms 154,472 KB
testcase_40	AC	361 ms 101,924 KB
testcase_41	AC	410 ms 122,988 KB
testcase_42	AC	530 ms 148,876 KB
testcase_43	AC	535 ms 125,520 KB
testcase_44	AC	568 ms 143,564 KB
testcase_45	AC	465 ms 90,384 KB
testcase_46	AC	660 ms 142,828 KB
testcase_47	AC	341 ms 113,588 KB
testcase_48	AC	497 ms 147,948 KB
testcase_49	AC	486 ms 149,232 KB
testcase_50	AC	340 ms 126,836 KB
testcase_51	AC	672 ms 145,692 KB
testcase_52	AC	391 ms 108,076 KB
testcase_53	AC	312 ms 107,040 KB
testcase_54	AC	412 ms 112,768 KB
testcase_55	AC	276 ms 107,148 KB
testcase_56	AC	270 ms 108,764 KB
testcase_57	AC	314 ms 102,636 KB
testcase_58	AC	429 ms 88,352 KB
testcase_59	AC	240 ms 99,564 KB
testcase_60	AC	329 ms 102,796 KB
testcase_61	AC	207 ms 82,132 KB
testcase_62	AC	363 ms 98,460 KB
testcase_63	AC	282 ms 100,008 KB
testcase_64	AC	247 ms 87,544 KB
testcase_65	AC	417 ms 140,320 KB
testcase_66	AC	274 ms 93,892 KB
testcase_67	AC	379 ms 118,160 KB
testcase_68	AC	329 ms 95,236 KB
testcase_69	AC	458 ms 154,992 KB
testcase_70	AC	252 ms 102,232 KB
testcase_71	AC	268 ms 104,624 KB
testcase_72	AC	317 ms 82,240 KB
testcase_73	AC	353 ms 127,676 KB
testcase_74	AC	478 ms 138,856 KB
testcase_75	AC	326 ms 105,104 KB
testcase_76	AC	396 ms 125,960 KB
testcase_77	AC	462 ms 147,388 KB
testcase_78	AC	410 ms 97,512 KB
testcase_79	AC	407 ms 119,376 KB
testcase_80	AC	416 ms 121,576 KB
testcase_81	AC	364 ms 122,892 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
rr = sys.stdin

N = int(rr.readline())
A = list(map(int,rr.readline().split()))
prime = []
dat = [0] * (2 * 10 ** 3)
for i in range(2,2 * 10 ** 3):
    if dat[i] == 0:
        prime.append(i)
        for j in range(2 * i,2 * 10 ** 3,i):
            dat[j] = 1
n = len(prime)
_sum = [[0] * n for _ in range(N+1)]

bit = [0] * (N + 1)
def add(i,x):
    while i <= N:
        bit[i] += x
        i += i & -i
def fold(i):
    ans = 0
    while i > 0:
        ans += bit[i]
        i -= i & -i
    return ans

for i in range(N):
    if A[i] == 0:
        add(i+1,1)
        for j in range(n):
            _sum[i+1][j] = _sum[i][j]
        continue
    for j in range(n):
        p = prime[j]
        count = 0
        while A[i] % p == 0:
            count += 1
            A[i] //= p
        _sum[i+1][j] = _sum[i][j] + count
Q = int(rr.readline())
for _ in range(Q):
    P,l,r = map(int,rr.readline().split())
    if fold(r) - fold(l-1) > 0:
        print('Yes')
        continue
    flag = True
    for j in range(n):
        p = prime[j]
        count = 0
        while P % p == 0:
            count += 1
            P //= p
        if count > _sum[r][j] - _sum[l-1][j]:
            flag = False
            break
    if flag and P == 1:
        print('Yes')
    else:
        print('NO')

yukicoder

結果

テストケース

ソースコード