結果

問題 No.871 かえるのうた
コンテスト
ユーザー flippergo
提出日時 2026-02-22 11:35:30
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 1,836 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 326 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 125,384 KB
最終ジャッジ日時 2026-02-22 11:35:40
合計ジャッジ時間 7,846 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from bisect import bisect_left,bisect_right
N,K = map(int,input().split())
X = list(map(int,input().split()))
A = list(map(int,input().split()))
INFTY = 2*10**17
M = 0
while pow(2,M)<N:
    M += 1
#区間最小値
Amin = [INFTY for _ in range(N)]
Amin[-1] = X[-1]-A[-1]
for i in range(N-2,-1,-1):
    Amin[i] = min(X[i]-A[i],Amin[i+1])
dpmin = [[INFTY for _ in range(N)] for _ in range(M+1)]
for i in range(N):
    dpmin[0][i] = X[i]-A[i]
for m in range(1,M+1):
    for i in range(N):
        if i+pow(2,m)>N:
            dpmin[m][i] = Amin[i]
        else:
            dpmin[m][i] = min(dpmin[m-1][i],dpmin[m-1][i+pow(2,m-1)])
def minq(i,j):#区間[i,j)の最小値
    d = j-i
    ans = INFTY
    ix = i
    for m in range(M,-1,-1):
        if d>>m & 1:
            ans = min(ans,dpmin[m][ix])
            ix = ix+(1<<m)
    return ans
#区間最大値
Amax = [-INFTY for _ in range(N)]
Amax[-1] = X[-1]+A[-1]
for i in range(N-2,-1,-1):
    Amax[i] = max(X[i]+A[i],Amax[i+1])
dpmax = [[-INFTY for _ in range(N)] for _ in range(M+1)]
for i in range(N):
    dpmax[0][i] = X[i]+A[i]
for m in range(1,M+1):
    for i in range(N):
        if i+pow(2,m)>N:
            dpmax[m][i] = Amax[i]
        else:
            dpmax[m][i] = max(dpmax[m-1][i],dpmax[m-1][i+pow(2,m-1)])
def maxq(i,j):#区間[i,j)の最大値
    d = j-i
    ans = -INFTY
    ix = i
    for m in range(M,-1,-1):
        if d>>m & 1:
            ans = max(ans,dpmax[m][ix])
            ix = ix+(1<<m)
    return ans
xmax = -INFTY
xmin = INFTY
K -= 1
ind_low = K
ind_high = K+1
while True:
    low = minq(ind_low,ind_high)
    high = maxq(ind_low,ind_high)
    if xmin<=low and xmax>=high:
        break
    if xmin>low:
        xmin = low
    if xmax<high:
        xmax = high
    ind_low = bisect_left(X,xmin)
    ind_high = bisect_right(X,xmax)
print(ind_high-ind_low)
0