結果

問題 No.2627 Unnatural Pitch
ユーザー 👑 AngrySadEightAngrySadEight
提出日時 2024-02-08 13:38:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 378 ms / 4,000 ms
コード長 1,326 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 261,696 KB
最終ジャッジ日時 2024-09-28 12:44:46
合計ジャッジ時間 7,914 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
54,328 KB
testcase_01 AC 38 ms
54,144 KB
testcase_02 AC 161 ms
202,304 KB
testcase_03 AC 38 ms
54,748 KB
testcase_04 AC 345 ms
261,696 KB
testcase_05 AC 347 ms
261,472 KB
testcase_06 AC 233 ms
193,340 KB
testcase_07 AC 153 ms
100,272 KB
testcase_08 AC 181 ms
130,232 KB
testcase_09 AC 306 ms
241,372 KB
testcase_10 AC 305 ms
240,996 KB
testcase_11 AC 68 ms
73,072 KB
testcase_12 AC 80 ms
77,356 KB
testcase_13 AC 42 ms
60,324 KB
testcase_14 AC 67 ms
73,340 KB
testcase_15 AC 67 ms
73,284 KB
testcase_16 AC 257 ms
163,720 KB
testcase_17 AC 378 ms
256,572 KB
testcase_18 AC 279 ms
143,012 KB
testcase_19 AC 305 ms
196,008 KB
testcase_20 AC 147 ms
101,260 KB
testcase_21 AC 240 ms
193,548 KB
testcase_22 AC 317 ms
216,176 KB
testcase_23 AC 224 ms
181,400 KB
testcase_24 AC 189 ms
113,216 KB
testcase_25 AC 264 ms
181,404 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

N, K, L, U = map(int, input().split())
A = list(map(int, input().split()))

assert 1 <= N <= 200000
assert 1 <= K <= 200000
assert 0 <= L <= 10 ** 12
assert 0 <= U <= 10 ** 12
assert U - L >= K
for i in range(N):
    assert 0 <= A[i] <= 10 ** 12

diffs = U - L
ok = 0
ng = 1000000000000002

while ng - ok > 1:
    mid = (ok + ng) // 2
    lower = 0
    upper = 0
    for i in range(N):
        if A[i] < mid:
            lower += 1
        elif A[i] > mid + diffs:
            upper += 1
    if lower <= upper:
        ok = mid
    else:
        ng = mid

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

ans = 10 ** 18 + 2

now_score = 0
now_L = ok - K
now_U = now_L + diffs

left_rem = [0 for _ in range(K)]
right_rem = [0 for _ in range(K)]

for i in range(N):
    if A[i] < now_L:
        now_score += (now_L - A[i] + K - 1) // K
        left_rem[A[i] % K] += 1
    if A[i] > now_U:
        now_score += (A[i] - now_U + K - 1) // K
        right_rem[A[i] % K] += 1

ans = min(ans, now_score)

for i in range(2 * K):
    left_rem[(now_L % K + K) % K] += d[now_L]
    now_score += left_rem[(now_L % K + K) % K]
    now_L += 1
    now_U += 1
    now_score -= right_rem[(now_U % K + K) % K]
    right_rem[(now_U % K + K) % K] -= d[now_U]
    ans = min(ans, now_score)

print(ans)
0