AtCoder Beginner Contest 221 D – Online games をPython3で解く

# AtCoder Beginner Contest 221 D - Online games
# https://atcoder.jp/contests/abc221/tasks/abc221_d
# tag: 座標圧縮 いもす法 典型問題 高橋君

# いもす法と呼ばれる手法で解く。

# A B で表されるプレイヤーがいる場合、人数の変化に着目すると
# A 日目の変化は +1、A+B 日目の変化は -1 となる。

# 日付ごとの変化量を記録するリストを用意しておき、
# 上記の変化をまとめていくことで、日付ごとの
# 人数の変化を作成することが可能。

# 今度は逆に日付ごとに順番に見ていき、現在の人数に
# 人数の変化を加えることで、その日付に何人いるのかを
# 把握することができる。

# 入力例 1 でいうと、作成される変化のリストは
# [0, 1, 1, 0, -1, -1] となり、その累積和
#  0, 1, 2, 2, 1, 0 が、実際の人数となる。

# のだが、日付の制約が緩く、全ての日付分の
# リストを作成すると TLE になってしまう。

# よって、まず日付を座標圧縮した後、いもす法を
# 用いる形で解く

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

    # 座標圧縮の準備。全ての座標をリストにする。
    day_list = []
    for a, b in players:
        day_list.append(a)
        day_list.append(a + b)

    # 重複をなくし、ソートする。
    # 圧縮後 → 圧縮前が day_list[i] で求まるようになる。
    day_list = list(set(day_list))
    day_list.sort()

    # 圧縮前 → 圧縮後が comp_dic[day] で求まるよう、辞書を作成。
    comp_dic = {day:i for i, day in enumerate(day_list)}

    # 圧縮後の座標を利用して、いもす法を行う。
    imos = [0] * len(day_list)
    for a, b in players:
        imos[comp_dic[a]] += 1
        imos[comp_dic[a + b]] -= 1

    result = [0] * (N+1)

    # いもす法で人数と経過した日数を求めていく。
    num = 0
    prev_day = 0
    for i in range(len(day_list)):
        now = day_list[i]
        result[num] += now - prev_day

        num += imos[i]
        prev_day = now

    print(*result[1:])

main()