結果

問題 No.2501 Maximum Inversion Number
ユーザー suisen
提出日時 2023-07-12 19:09:36
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 996 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 138,028 KB
最終ジャッジ日時 2024-10-01 18:42:57
合計ジャッジ時間 11,625 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from typing import List
def main(_: int, m: int, l: List[int], r: List[int]):
if not (sum(l) <= m <= sum(r)):
return -1
if m == sum(l):
return (m * m - sum(e * e for e in l)) // 2
def clamp(v: int, l: int, r: int):
return max(l, min(v, r))
def get_sum(t: int):
return sum(clamp(t, a, b) for a, b in zip(l, r))
tl, tr = 0, 10 ** 9 + 10
while abs(tr - tl) > 1:
t = (tl + tr) // 2
if get_sum(t) < m:
tl = t
else:
tr = t
t0, d = tl, m - get_sum(tl)
x = 0
for a, b in zip(l, r):
c = clamp(t0, a, b)
if d > 0 and a <= t0 < b:
c += 1
d -= 1
x += c * c
return (m * m - x) // 2
if __name__ == '__main__':
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
l = list(map(int, input().split()))
r = list(map(int, input().split()))
print(main(n, m, l, r))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0