結果

問題 No.1194 Replace
ユーザー gew1fw
提出日時 2025-06-12 18:14:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 765 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 237,732 KB
最終ジャッジ日時 2025-06-12 18:15:24
合計ジャッジ時間 13,757 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

n, m = map(int, input().split())

operations = []
s = set()

for _ in range(m):
    b, c = map(int, input().split())
    operations.append((b, c))
    s.add(b)
    s.add(c)

sorted_list = sorted(s, reverse=True)

b_to_c = defaultdict(list)
for b, c in operations:
    b_to_c[b].append(c)

max_reach = {x: x for x in sorted_list}

for x in sorted_list:
    cs = b_to_c.get(x, [])
    if not cs:
        continue
    current_max = max(max_reach.get(c, c) for c in cs)
    if current_max > max_reach[x]:
        max_reach[x] = current_max

sum_increment = 0
for x in sorted_list:
    if 1 <= x <= n and max_reach[x] > x:
        sum_increment += (max_reach[x] - x)

initial_sum = n * (n + 1) // 2
print(initial_sum + sum_increment)
0