ABC188D - Snuke Prime

方法1：

考え方

$a, b$をイベント発生日としてまとめて扱い，イベント発生日を小さい順に考えると簡単に処理できる．
Editorial - AtCoder Beginner Contest 188

方法2：座標圧縮+いもす法

考え方

日をindexにした累積和accが求められれば，

ans = 0
for i in range(len(acc) - 1):
  ans += min(C, acc[i]) * ((i + 1) - i)

という感じで答えを計算できる．

しかし，日として取り得る値が$1 \sim 10^{9}$なので，座標圧縮をする必要がある．

累積和はいもす法で計算できるが，$b_{i}$ではなく$b_{i} + 1$日が必要になることに注意．

回答例

N, C = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(N)]

days = set()
for a, b, c in ABC:
    if a not in days:
        days.add(a)
    if b + 1 not in days:
        days.add(b + 1)
days = sorted(list(days))

dict = {x:i for i, x in enumerate(days)}

acc = [0] * (len(days))
for a, b, c in ABC:
    acc[dict[a]] += c
    acc[dict[b + 1]] -= c

for i in range(len(days) - 1):
    acc[i + 1] += acc[i]

ans = 0
for i in range(len(days) - 1):
    ans += min(C, acc[i]) * (days[i + 1] - days[i])

print(ans)