結果
問題 | No.2698 Many Asakatsu |
ユーザー |
|
提出日時 | 2024-03-16 05:17:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 527 ms / 2,000 ms |
コード長 | 1,112 bytes |
コンパイル時間 | 148 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 99,588 KB |
最終ジャッジ日時 | 2024-09-30 05:57:53 |
合計ジャッジ時間 | 9,114 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from sys import stdin, setrecursionlimitfrom collections import dequeimport bisectinput = stdin.readlinereadline = stdin.readlineN,M=map(int, input().split())kousa=[]syoko=[]for i in range(N):s,k=map(int,input().split())kousa.append(k)syoko.append(s)def SuMD(i:int,p:int):if p==0:return 0return syoko[i]*p+p*(p-1)//2*kousa[i]def f_i(i:int,x:int):if x<=syoko[i]:p=0elif x>syoko[i]+kousa[i]*(M-1):p=Melse:p=(x-syoko[i]-1)//kousa[i]+1return (SuMD(i,M)-2*SuMD(i,p))+(2*p-M)*xdef CH(i:int,j:int,k:int)->bool:L,R=0,10**9+1while R-L>1:mid=(L+R)//2if f_i(j,mid)<=f_i(k,mid):L=midelse:R=midif f_i(i,R-1)<=f_i(j,R-1):return Trueelse:return Falsed=deque()dlen=0for i in range(N):while dlen>=2 and CH(d[-2],d[-1],i):d.pop()dlen-=1d.append(i)dlen+=1Q,X=map(int,input().split())A=list(map(int, input().split()))AN=[0]*Qfor q in range(Q):while dlen>=2 and f_i(d[0],X)>f_i(d[1],X):dlen-=1d.popleft()AN[q]=d[0]+1X+=A[AN[q]-1]if X>10**9+5:X=10**9+5print(*AN)