結果

問題 No.817 Coin donation
コンテスト
ユーザー Kohei
提出日時 2026-07-12 21:44:25
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 220 ms / 2,000 ms
+ 78µs
コード長 984 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 236 ms
コンパイル使用メモリ 95,724 KB
実行使用メモリ 137,996 KB
最終ジャッジ日時 2026-07-12 21:45:48
合計ジャッジ時間 3,237 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#from collections import defaultdict
N, K = map(int, input().split())
K -= 1
shikiri = set()
LR = []
for i in range(N):
    a, b = map(int, input().split())
    shikiri.add(a)
    shikiri.add(b + 1)
    LR.append((a, b + 1))

nums = sorted(shikiri)
d = {}
id = 0
for num in nums:
    d[num] = id
    id += 1

L = len(d)
cnt = [0] * (L + 1)

for l, r in LR:
    l = d[l]
    r = d[r]
    cnt[l] += 1
    cnt[r] -= 1

# 左から累積
for i in range(L):
    cnt[i + 1] += cnt[i]
# nums と cnt で答えが出せる

total = 0
for i in range(L - 1):
    pos, nex = nums[i], nums[i + 1]
    # pos ~ nex - 1 までの nex - 1 - (pos - 1) = nex - pos 個の整数が cnt[i] 個*ずつ*存在する
    subtotal = (nex - pos) * cnt[i]
    
    if total + subtotal < K: # 次の区間に行く
        total += subtotal
    else: # この区間にK番目が存在する
        nokori = K - total
        sho, amari = divmod(nokori, cnt[i])
        ans = pos + sho
        exit(print(ans))
0