結果

問題 No.1012 荷物収集
コンテスト
ユーザー prd_xxx
提出日時 2020-03-20 23:05:55
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 755 ms / 2,000 ms
コード長 924 bytes
コンパイル時間 81 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 53,644 KB
最終ジャッジ日時 2024-12-15 08:17:11
合計ジャッジ時間 16,593 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
XW = [tuple(map(int,input().split())) for i in range(N)]
XW.sort(key=lambda x:x[0])
X = list(map(int,input().split()))

lc = [0]
wc = [0]
for (px,pw),(x,_) in zip(XW,XW[1:]):
    wc.append(wc[-1] + pw)
    lc.append(lc[-1] + wc[-1] * (x-px))
wc.append(wc[-1] + XW[-1][1])
xs = [x for x,_ in XW]

XW.reverse()
rc = [0]
w = 0
for (px,pw),(x,_) in zip(XW,XW[1:]):
    w += pw
    rc.append(rc[-1] + w * (px-x))
rc.reverse()

from bisect import bisect
ans = []
for x in X:
    i = bisect(xs, x)
    if i and xs[i-1] == x:
        ans.append(lc[i-1] + rc[i-1])
        continue
    if i==0:
        ans.append(rc[0] + wc[-1]*(xs[0]-x))
        continue
    if i==N:
        ans.append(lc[-1] + wc[-1]*(x-xs[-1]))
        continue
    l,r = x-xs[i-1], xs[i]-x
    v = lc[i-1] + rc[i]
    v += l*wc[i] + r*(wc[-1] - wc[i])
    ans.append(v)
print(*ans, sep='\n')
0