結果
問題 | No.2698 Many Asakatsu |
ユーザー | karinohito |
提出日時 | 2024-03-16 05:21:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 721 ms / 2,000 ms |
コード長 | 1,492 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 96,672 KB |
最終ジャッジ日時 | 2024-03-20 03:04:18 |
合計ジャッジ時間 | 11,360 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
55,600 KB |
testcase_01 | AC | 40 ms
55,600 KB |
testcase_02 | AC | 40 ms
55,600 KB |
testcase_03 | AC | 39 ms
55,600 KB |
testcase_04 | AC | 40 ms
55,600 KB |
testcase_05 | AC | 41 ms
55,600 KB |
testcase_06 | AC | 41 ms
55,600 KB |
testcase_07 | AC | 93 ms
75,924 KB |
testcase_08 | AC | 89 ms
75,800 KB |
testcase_09 | AC | 87 ms
75,796 KB |
testcase_10 | AC | 83 ms
75,932 KB |
testcase_11 | AC | 153 ms
77,688 KB |
testcase_12 | AC | 142 ms
77,208 KB |
testcase_13 | AC | 130 ms
76,936 KB |
testcase_14 | AC | 133 ms
76,948 KB |
testcase_15 | AC | 144 ms
77,204 KB |
testcase_16 | AC | 148 ms
77,412 KB |
testcase_17 | AC | 113 ms
76,696 KB |
testcase_18 | AC | 141 ms
77,076 KB |
testcase_19 | AC | 183 ms
83,908 KB |
testcase_20 | AC | 177 ms
83,124 KB |
testcase_21 | AC | 188 ms
83,772 KB |
testcase_22 | AC | 700 ms
96,332 KB |
testcase_23 | AC | 582 ms
95,032 KB |
testcase_24 | AC | 721 ms
95,416 KB |
testcase_25 | AC | 709 ms
96,188 KB |
testcase_26 | AC | 700 ms
96,672 KB |
testcase_27 | AC | 594 ms
94,440 KB |
testcase_28 | AC | 593 ms
93,900 KB |
testcase_29 | AC | 220 ms
94,152 KB |
testcase_30 | AC | 271 ms
94,644 KB |
testcase_31 | AC | 578 ms
93,412 KB |
testcase_32 | AC | 432 ms
95,684 KB |
testcase_33 | AC | 139 ms
83,356 KB |
testcase_34 | AC | 454 ms
93,196 KB |
ソースコード
from sys import stdin, setrecursionlimit input = stdin.readline readline = stdin.readline N,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 deque def ff(x,mid): p,q=B[x] if mid<=p: l=0 elif q==0: if mid>p: l=M else: l=min(M,(mid-p)//q+1) r=M-l ls=(p+p+q*(l-1))*l//2 rs=(p+p+q*(M-1))*M//2-ls return abs(l*mid-ls)+abs(r*mid-rs) def f(x,y): ok=0;ng=10**9+1 p,q=B[x];pp,qq=B[y] while abs(ok-ng)>1: mid=(ok+ng)//2 acum=ff(x,mid) bcum=ff(y,mid) if acum<=bcum: ok=mid else: ng=mid return ok d=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: break d.append(i) #print(d) C=list(d) now=0 def ff(x,mid): p,q=B[x] if mid<=p: l=0 elif q==0: if mid>p: l=M else: l=min(M,(mid-p)//q+1) r=M-l ls=(p+p+q*(l-1))*l//2 rs=(p+p+q*(M-1))*M//2-ls return abs(l*mid-ls)+abs(r*mid-rs) ans=[-1]*Q for q in range(Q): if now+1==N: ans[q]=C[now]+1 else: D=[] s=now for i in range(s,len(C)): p=C[i] D.append(ff(p,X)) if len(D)>1 and D[-2]<D[-1]: break if len(D)>1 and D[-2]>D[-1]: now=i ans[q]=C[now]+1 X+=A[ans[q]-1] print(*ans)