結果

問題 No.1194 Replace
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:39:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 992 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 81,856 KB
実行使用メモリ 206,824 KB
最終ジャッジ日時 2025-06-12 20:39:43
合計ジャッジ時間 7,351 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    m = int(data[1])
    index = 2
    
    max_c = {}
    for _ in range(m):
        b = int(data[index])
        c = int(data[index + 1])
        index += 2
        if b in max_c:
            if c > max_c[b]:
                max_c[b] = c
        else:
            max_c[b] = c

    parent = {}
    for x in max_c:
        c = max_c[x]
        if c > x:
            parent[x] = c
        else:
            parent[x] = x

    dp = {}

    def get_max(x):
        if x in dp:
            return dp[x]
        if x in max_c and max_c[x] > x:
            res = get_max(max_c[x])
            dp[x] = res
        else:
            dp[x] = x
        return dp[x]

    sum_diff = 0
    for x in max_c:
        y = get_max(x)
        sum_diff += (y - x)

    total = n * (n + 1) // 2 + sum_diff
    print(total)

if __name__ == "__main__":
    main()
0