#1034063 (PyPy3) No.2543 Many Meetings

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
## 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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX