結果

問題 No.1194 Replace
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:23:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,093 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 103,308 KB
最終ジャッジ日時 2025-03-31 17:24:18
合計ジャッジ時間 6,546 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, stdin.readline().split())
    max_map = {}

    for _ in range(M):
        B, C = map(int, stdin.readline().split())
        if C > B:
            if B not in max_map or max_map[B] < C:
                max_map[B] = C

    memo = {}

    def get_max(x):
        if x in memo:
            return memo[x]
        visited = []
        current = x
        while True:
            if current in memo:
                current = memo[current]
                break
            visited.append(current)
            if current in max_map:
                next_val = max_map[current]
                if next_val > current:
                    current = next_val
                else:
                    break
            else:
                break
        for node in visited:
            memo[node] = current
        return current

    sum_total = N * (N + 1) // 2

    for b in max_map:
        x = get_max(b)
        sum_total += (x - b)

    print(sum_total)

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