結果

問題 No.854 公平なりんご分配
ユーザー lam6er
提出日時 2025-03-20 20:37:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,078 ms / 3,153 ms
コード長 3,465 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 131,772 KB
最終ジャッジ日時 2025-03-20 20:38:43
合計ジャッジ時間 23,959 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
from collections import defaultdict

def get_primes(num):
    factors = {}
    temp = num
    if temp == 0:
        return factors
    for i in range(2, int(math.isqrt(temp)) + 1):
        while temp % i == 0:
            factors[i] = factors.get(i, 0) + 1
            temp //= i
        if temp == 1:
            break
    if temp > 1:
        factors[temp] = 1
    return factors

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    A = list(map(int, data[ptr:ptr+N]))
    ptr += N
    Q = int(data[ptr])
    ptr +=1
    queries = []
    for _ in range(Q):
        P = int(data[ptr])
        L = int(data[ptr+1])
        R = int(data[ptr+2])
        queries.append((P, L, R))
        ptr +=3
    
    # Precompute sum_zero
    sum_zero = [0]*(N+1)
    for i in range(1, N+1):
        sum_zero[i] = sum_zero[i-1] + (1 if A[i-1] == 0 else 0)
    
    # Collect all primes in A's factors
    prime_set = set()
    for num in A:
        if num ==0:
            continue
        factors = get_primes(num)
        for p in factors:
            prime_set.add(p)
    primes = sorted(prime_set)
    primes_set = set(primes)
    
    # Precompute events for each prime
    events = defaultdict(list)
    for idx in range(N):
        j = idx +1  # 1-based index
        num = A[idx]
        if num ==0:
            continue
        factors = get_primes(num)
        for p in factors:
            cnt = factors[p]
            if not events[p]:
                prev_sum =0
            else:
                prev_sum = events[p][-1][1]
            new_sum = prev_sum + cnt
            events[p].append( (j, new_sum) )
    
    def get_sum(p, pos):
        if p not in events:
            return 0
        lst = events[p]
        left, right = 0, len(lst) -1
        res =0
        while left <= right:
            mid = (left + right) //2
            j, s = lst[mid]
            if j <= pos:
                res = s
                left = mid +1
            else:
                right = mid -1
        return res
    
    # Process queries
    results = []
    for (P, L, R) in queries:
        if sum_zero[R] - sum_zero[L-1] >0:
            results.append("Yes")
            continue
        if P ==1:
            results.append("Yes")
            continue
        # Factorize P using primes from the set
        temp = P
        factors = {}
        possible = True
        for p in primes:
            if p*p > temp:
                break
            if temp % p ==0:
                cnt =0
                while temp % p ==0:
                    cnt +=1
                    temp //=p
                factors[p] = cnt
            if temp ==1:
                break
        if temp >1:
            if temp in primes_set:
                factors[temp] = factors.get(temp, 0) +1
            else:
                possible = False
        if not possible or not factors:
            results.append("NO" if not possible else "Yes")
            continue
        # Check each factor in factors
        for p in factors:
            required = factors[p]
            sum_R = get_sum(p, R)
            sum_L_minus_1 = get_sum(p, L-1)
            total = sum_R - sum_L_minus_1
            if total < required:
                possible = False
                break
        results.append("Yes" if possible else "NO")
    
    print('\n'.join(results))

if __name__ == '__main__':
    main()
0