結果
問題 | No.1012 荷物収集 |
ユーザー |
![]() |
提出日時 | 2020-03-21 00:11:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 444 ms / 2,000 ms |
コード長 | 1,369 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 136,296 KB |
最終ジャッジ日時 | 2024-12-15 21:48:47 |
合計ジャッジ時間 | 11,845 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
n, q = map(int, input().split()) info = [list(map(int, input().split())) for i in range(n)] query = list(map(int, input().split())) memo = {query[i]: i for i in range(q)} query = sorted(query) after_memo = {query[i]: i for i in range(q)} info = sorted(info) ans = [0] * q ind = 0 weight = 0 for i in range(q): tmp = 0 pos = query[i] if i - 1 >= 0: prv_pos = query[i - 1] else: prv_pos = pos while True: if ind >= n: break x, w = info[ind] if x <= pos: tmp += w ans[i] += w * (pos - x) ind += 1 else: break if i - 1 >= 0: ans[i] += (pos - prv_pos) * weight + ans[i - 1] weight += tmp ans2 = [0] * q ind = n - 1 weight = 0 for i in range(q)[::-1]: tmp = 0 pos = query[i] if i + 1 < q: prv_pos = query[i + 1] else: prv_pos = pos while True: if ind < 0: break x, w = info[ind] if x >= pos: tmp += w ans2[i] += w * abs(pos - x) ind -= 1 else: break if i + 1 < q: ans2[i] += abs(pos - prv_pos) * weight + ans2[i + 1] weight += tmp res = [0] * q for i in range(q): res[memo[query[i]]] = ans[after_memo[query[i]]] + ans2[after_memo[query[i]]] for i in range(q): print(res[i])