AtCoder Beginner Contest 061 C – Big Array をPython3で解く

# AtCoder Beginner Contest 061 C- Big Array
# https://atcoder.jp/contests/abc061/tasks/abc061_c
# tag: 考察

# 制約が大きいので、馬鹿正直に配列に数字を一個一個入れていくのはよくない。
# 下手すると 10^5 個の数字を 10^5 回入れた上で、ソートする羽目になる。
# 入れた数字の種類と個数だけを保存しておくのがいいだろう。
# 最終的に種類だけでソートし、後はそれぞれの数字が入っている個数を
# 確認しながら、上から K 番目の数字を確認すればいい。

def main():
    N, K = map(int, input().split())
    inserts = [list(map(int, input().split())) for _ in range(N)]

    # カウント用の辞書を用意
    counter = {}

    # 順に見ていき、最終的に何がいくつ入っているのかをカウントしておく
    for num, volume in inserts:
        if num not in counter:
            counter[num] = 0
        counter[num] += volume
    
    checked = 0

    # 入っている数字をソートしつつ順に取り出していく
    for num in sorted(counter.keys()):
        # 求める順位が次の数字の個数で達成できるなら、その数字を回答
        if checked <=  K <= checked + counter[num]:
            print(num)
            return
        # 足りないなら、数字の個数をチェック済みとして、次の数字を見る
        checked += counter[num]

main()