結果

問題 No.2197 Same Dish
ユーザー lam6er
提出日時 2025-03-20 18:58:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 408 ms / 2,000 ms
コード長 886 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 109,340 KB
最終ジャッジ日時 2025-03-20 18:59:46
合計ジャッジ時間 5,155 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    K = int(data[idx+1])
    idx += 2
    
    guests = []
    for _ in range(N):
        L = int(data[idx])
        R = int(data[idx+1])
        guests.append((L, R))
        idx += 2
    
    # Sort guests by L_i
    guests.sort()
    
    heap = []
    res = 1
    for L, R in guests:
        Li_10 = L * 10
        # Remove all guests where Rj_after <= Li_10
        while heap and heap[0] <= Li_10:
            heapq.heappop(heap)
        m = len(heap)
        if K - m <= 0:
            res = 0
            break
        res = (res * (K - m)) % MOD
        Rj_after = R * 10 - 1
        heapq.heappush(heap, Rj_after)
    
    total = pow(K, N, MOD)
    ans = (total - res) % MOD
    print(ans)

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