結果

問題 No.2543 Many Meetings
ユーザー LyricalMaestroLyricalMaestro
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
54,272 KB
testcase_01 AC 51 ms
54,144 KB
testcase_02 AC 54 ms
54,400 KB
testcase_03 AC 1,353 ms
234,332 KB
testcase_04 AC 1,333 ms
234,484 KB
testcase_05 AC 1,335 ms
234,484 KB
testcase_06 AC 1,309 ms
234,672 KB
testcase_07 AC 1,329 ms
234,216 KB
testcase_08 AC 1,176 ms
234,588 KB
testcase_09 AC 1,238 ms
235,484 KB
testcase_10 AC 1,222 ms
234,836 KB
testcase_11 AC 1,159 ms
234,460 KB
testcase_12 AC 1,191 ms
235,732 KB
testcase_13 AC 1,093 ms
201,232 KB
testcase_14 AC 689 ms
158,916 KB
testcase_15 AC 711 ms
157,000 KB
testcase_16 AC 941 ms
183,476 KB
testcase_17 AC 1,152 ms
193,032 KB
testcase_18 AC 1,260 ms
205,420 KB
testcase_19 AC 1,170 ms
197,276 KB
testcase_20 AC 1,213 ms
200,524 KB
testcase_21 AC 1,416 ms
222,720 KB
testcase_22 AC 1,132 ms
193,060 KB
testcase_23 AC 89 ms
72,844 KB
testcase_24 AC 55 ms
62,848 KB
testcase_25 AC 64 ms
65,640 KB
testcase_26 AC 102 ms
69,248 KB
testcase_27 AC 90 ms
74,240 KB
testcase_28 AC 432 ms
122,528 KB
testcase_29 AC 244 ms
89,984 KB
testcase_30 AC 255 ms
91,844 KB
testcase_31 AC 222 ms
88,576 KB
testcase_32 AC 362 ms
112,188 KB
testcase_33 AC 48 ms
54,160 KB
testcase_34 AC 47 ms
54,576 KB
testcase_35 AC 46 ms
54,592 KB
testcase_36 AC 46 ms
54,484 KB
testcase_37 AC 46 ms
54,400 KB
testcase_38 AC 47 ms
54,656 KB
testcase_39 AC 47 ms
54,656 KB
testcase_40 AC 46 ms
54,528 KB
testcase_41 AC 46 ms
54,520 KB
testcase_42 AC 52 ms
54,300 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(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