結果

問題 No.2543 Many Meetings
ユーザー LyricalMaestro
提出日時 2025-01-03 13:22:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,416 ms / 2,000 ms
コード長 2,026 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 235,732 KB
最終ジャッジ日時 2025-01-03 13:22:58
合計ジャッジ時間 28,036 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2543

import heapq
from collections import deque

MAX_INT = 10 ** 18

def main():
    N, K = map(int, input().split())
    lr = []
    for _ in range(N):
        l, r = map(int, input().split())
        lr.append((l, r))

    # l, rについて並び替える
    l_map = {}
    r_map = {}
    for i in range(N):
        l, r = lr[i]
        if l not in l_map:
            l_map[l] = []
        l_map[l].append((r, i))

        if r not in r_map:
            r_map[r] = []
        r_map[r].append(i)

    # イベント発生時系列順に並べる
    events = set()    
    for i in range(N):
        l, r = lr[i]
        events.add(l)
        events.add(r)
    events = list(events)
    events.sort()

    # 次
    next_nodes = [-1 for _ in range(N)]
    queue = []
    for x in reversed(events):
        if x in l_map:
            for r, i in l_map[x]:
                heapq.heappush(queue, (r, -x, i))


        if len(queue) > 0 and x in r_map:
            for i in r_map[x]:
                _, _, i0 = queue[0]
                next_nodes[i] = i0
    
    # ダブリング
    max_k = 0
    while (1 << max_k) < K:
        max_k += 1
    max_k += 1
    next_nodes_list = [[-1] * N for _ in range(max_k + 1)]
    next_nodes_list[0] = next_nodes
    for k in range(1, max_k + 1):
        for i in range(N):
            n = next_nodes_list[k - 1][i]
            if n != -1:
                next_nodes_list[k][i] = next_nodes_list[k - 1][n]
    
    answer = MAX_INT
    for i in range(N):
        k0 = K - 1
        v = i
        for k in reversed(range(max_k + 1)):
            if k0 >= (1 << k):
                if next_nodes_list[k][v] != -1:
                    v = next_nodes_list[k][v]
                    k0 -= (1 << k)

        if k0 == 0:
            l0, _ = lr[i]
            _, r0 = lr[v]
            ans = r0 - l0
            answer = min(answer, ans)
    if answer == MAX_INT:
        print(-1)
    else:
        print(answer)







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