結果
問題 | No.2698 Many Asakatsu |
ユーザー | 👑 timi |
提出日時 | 2024-03-16 12:56:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 746 ms / 2,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 284 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 107,064 KB |
最終ジャッジ日時 | 2024-03-20 03:04:23 |
合計ジャッジ時間 | 11,510 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
55,600 KB |
testcase_01 | AC | 39 ms
55,600 KB |
testcase_02 | AC | 41 ms
55,600 KB |
testcase_03 | AC | 39 ms
55,600 KB |
testcase_04 | AC | 39 ms
55,600 KB |
testcase_05 | AC | 41 ms
55,600 KB |
testcase_06 | AC | 41 ms
55,600 KB |
testcase_07 | AC | 94 ms
75,924 KB |
testcase_08 | AC | 88 ms
75,800 KB |
testcase_09 | AC | 87 ms
75,796 KB |
testcase_10 | AC | 83 ms
75,932 KB |
testcase_11 | AC | 149 ms
77,688 KB |
testcase_12 | AC | 144 ms
77,208 KB |
testcase_13 | AC | 128 ms
76,936 KB |
testcase_14 | AC | 134 ms
76,948 KB |
testcase_15 | AC | 146 ms
77,204 KB |
testcase_16 | AC | 148 ms
77,412 KB |
testcase_17 | AC | 113 ms
76,696 KB |
testcase_18 | AC | 138 ms
77,076 KB |
testcase_19 | AC | 203 ms
88,772 KB |
testcase_20 | AC | 184 ms
90,240 KB |
testcase_21 | AC | 196 ms
87,612 KB |
testcase_22 | AC | 709 ms
103,368 KB |
testcase_23 | AC | 590 ms
97,744 KB |
testcase_24 | AC | 746 ms
102,840 KB |
testcase_25 | AC | 702 ms
102,064 KB |
testcase_26 | AC | 694 ms
100,032 KB |
testcase_27 | AC | 591 ms
104,296 KB |
testcase_28 | AC | 601 ms
103,860 KB |
testcase_29 | AC | 219 ms
94,396 KB |
testcase_30 | AC | 275 ms
107,064 KB |
testcase_31 | AC | 576 ms
99,364 KB |
testcase_32 | AC | 435 ms
104,512 KB |
testcase_33 | AC | 145 ms
87,668 KB |
testcase_34 | AC | 427 ms
98,316 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=[] for i in range(Q): if i==0: x=X if now+1==N: ans.append(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.append(C[now]+1) x+=A[C[now]] print(*ans)