結果
問題 | No.2698 Many Asakatsu |
ユーザー |
![]() |
提出日時 | 2024-03-16 12:56:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 652 ms / 2,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 129 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 107,324 KB |
最終ジャッジ日時 | 2024-09-30 05:58:24 |
合計ジャッジ時間 | 10,124 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from sys import stdin, setrecursionlimitinput = stdin.readlinereadline = stdin.readlineN,M=map(int, input().split())B=[]for i in range(N):a,b=map(int, input().split())B.append((a,b))Q,X=map(int, input().split())A=list(map(int, input().split()))from collections import dequedef ff(x,mid):p,q=B[x]if mid<=p:l=0elif q==0:if mid>p:l=Melse:l=min(M,(mid-p)//q+1)r=M-lls=(p+p+q*(l-1))*l//2rs=(p+p+q*(M-1))*M//2-lsreturn abs(l*mid-ls)+abs(r*mid-rs)def f(x,y):ok=0;ng=10**9+1p,q=B[x];pp,qq=B[y]while abs(ok-ng)>1:mid=(ok+ng)//2acum=ff(x,mid)bcum=ff(y,mid)if acum<=bcum:ok=midelse:ng=midreturn okd=deque()for i in range(N):a,b=B[i]if len(d)<2:d.append(i)else:while len(d)>1:x,y=d[-2],d[-1]k=f(y,i)if ff(x,k)<=ff(y,k):d.pop()else:breakd.append(i)#print(d)C=list(d)now=0def ff(x,mid):p,q=B[x]if mid<=p:l=0elif q==0:if mid>p:l=Melse:l=min(M,(mid-p)//q+1)r=M-lls=(p+p+q*(l-1))*l//2rs=(p+p+q*(M-1))*M//2-lsreturn abs(l*mid-ls)+abs(r*mid-rs)ans=[]for i in range(Q):if i==0:x=Xif now+1==N:ans.append(C[now]+1)else:D=[]s=nowfor i in range(s,len(C)):p=C[i]D.append(ff(p,x))if len(D)>1 and D[-2]<D[-1]:breakif len(D)>1 and D[-2]>D[-1]:now=ians.append(C[now]+1)x+=A[C[now]]print(*ans)