結果

問題 No.3284 Picnic with Friends
ユーザー hirayuu_yc
提出日時 2025-09-23 00:37:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,840 ms / 7,000 ms
コード長 1,223 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 168,156 KB
最終ジャッジ日時 2025-09-26 20:52:20
合計ジャッジ時間 67,693 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import isqrt
B=500000

def enum_quot(n):
    x=isqrt(n)
    ret=list(range(1,x+1))
    for i in range(x,0,-1):
        if ret[-1]!=n//i:
            ret.append(n//i)
    return ret
        

N=int(input())
S=list(map(int,input().split()))
Q=int(input())
event=[tuple(map(int,input().split())) for i in range(Q)]
event.sort()
A=[]
now=0
end=0
for t,f in event:
    if now==0:
        end=f+t
        now=f
    else:
        if t<=end:
            end+=f
            now+=f
        else:
            A.append(now)
            end=f+t
            now=f
A.append(now)
small=[0]*B
large=[]
for a in A:
    quots=enum_quot(a)[::-1]
    quots.append(0)
    small[0]+=quots[0]
    for i in range(len(quots)-1):
        if a//quots[i]+1<B:
            small[a//quots[i]+1]+=quots[i+1]-quots[i]
        else:
            large.append((a//quots[i]+1,quots[i+1]-quots[i]))
large.append((1<<60,0))
large.sort(reverse=True)
fin=[0]*N
s=[(S[i],i) for i in range(N)]
s.sort()
for i in range(1,B):
    small[i]+=small[i-1]
now=small[-1]
for v,id in s:
    if v<B:
        fin[id]=small[v]
    else:
        while large[-1][0]<=v:
            now+=large[-1][1]
            large.pop()
        fin[id]=now
for i in fin:
    print(i)
0