結果

問題 No.2543 Many Meetings
ユーザー LyricalMaestroLyricalMaestro
提出日時 2025-01-03 13:11:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,021 bytes
コンパイル時間 415 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 244,200 KB
最終ジャッジ日時 2025-01-03 13:12:30
合計ジャッジ時間 31,078 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
54,272 KB
testcase_01 AC 52 ms
54,528 KB
testcase_02 AC 53 ms
54,528 KB
testcase_03 AC 1,398 ms
242,948 KB
testcase_04 AC 1,343 ms
243,084 KB
testcase_05 AC 1,337 ms
242,832 KB
testcase_06 AC 1,343 ms
243,204 KB
testcase_07 AC 1,482 ms
242,560 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 205 ms
89,728 KB
testcase_30 WA -
testcase_31 AC 233 ms
89,472 KB
testcase_32 AC 424 ms
115,752 KB
testcase_33 AC 50 ms
54,528 KB
testcase_34 AC 50 ms
54,400 KB
testcase_35 AC 46 ms
54,656 KB
testcase_36 AC 48 ms
54,656 KB
testcase_37 AC 46 ms
54,272 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 51 ms
54,656 KB
testcase_41 AC 51 ms
54,400 KB
testcase_42 AC 53 ms
54,656 KB
権限があれば一括ダウンロードができます

ソースコード

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((l, 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 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