結果

問題 No.2543 Many Meetings
ユーザー titiatitia
提出日時 2023-11-26 03:34:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,464 ms / 2,000 ms
コード長 1,286 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 224,688 KB
最終ジャッジ日時 2024-09-26 11:27:47
合計ジャッジ時間 26,947 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
53,504 KB
testcase_01 AC 43 ms
53,504 KB
testcase_02 AC 48 ms
53,376 KB
testcase_03 AC 1,222 ms
223,692 KB
testcase_04 AC 1,214 ms
221,848 KB
testcase_05 AC 1,255 ms
224,688 KB
testcase_06 AC 1,213 ms
222,644 KB
testcase_07 AC 1,213 ms
222,452 KB
testcase_08 AC 1,290 ms
222,896 KB
testcase_09 AC 1,276 ms
222,132 KB
testcase_10 AC 1,276 ms
221,068 KB
testcase_11 AC 1,247 ms
223,156 KB
testcase_12 AC 1,274 ms
222,288 KB
testcase_13 AC 1,016 ms
189,628 KB
testcase_14 AC 586 ms
138,028 KB
testcase_15 AC 563 ms
137,040 KB
testcase_16 AC 879 ms
175,088 KB
testcase_17 AC 981 ms
186,268 KB
testcase_18 AC 1,030 ms
192,572 KB
testcase_19 AC 966 ms
188,924 KB
testcase_20 AC 959 ms
187,712 KB
testcase_21 AC 1,464 ms
207,068 KB
testcase_22 AC 1,171 ms
186,828 KB
testcase_23 AC 81 ms
72,448 KB
testcase_24 AC 56 ms
63,104 KB
testcase_25 AC 60 ms
64,896 KB
testcase_26 AC 66 ms
67,328 KB
testcase_27 AC 84 ms
74,240 KB
testcase_28 AC 531 ms
103,144 KB
testcase_29 AC 226 ms
83,328 KB
testcase_30 AC 223 ms
83,968 KB
testcase_31 AC 87 ms
79,860 KB
testcase_32 AC 129 ms
88,940 KB
testcase_33 AC 41 ms
53,248 KB
testcase_34 AC 43 ms
52,864 KB
testcase_35 AC 42 ms
53,376 KB
testcase_36 AC 44 ms
53,248 KB
testcase_37 AC 42 ms
53,248 KB
testcase_38 AC 44 ms
53,504 KB
testcase_39 AC 41 ms
53,504 KB
testcase_40 AC 41 ms
53,504 KB
testcase_41 AC 40 ms
53,120 KB
testcase_42 AC 43 ms
53,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect

N,K=map(int,input().split())
LR=[list(map(int,input().split())) for i in range(N)]

if K==1:
    ANS=1<<60
    for x,y in LR:
        ANS=min(ANS,y-x)

    print(ANS)
    exit()

E=dict()

LR1=sorted(LR,key=itemgetter(0))
LR2=sorted(LR,key=itemgetter(1))

ind=N-1
MIN=1<<60

for x,y in LR2[::-1]:
    while ind>=0 and LR1[ind][0]>=y:
        MIN=min(MIN,LR1[ind][1])
        ind-=1

    E[y]=MIN

LIST=[]

for x in E:
    if E[x]!=1<<60:
        LIST.append((x,E[x]))

LIST.sort(key=itemgetter(0))

A=[-1]*len(LIST)

for i in range(len(LIST)):
    x,y=LIST[i]
    k=bisect(LIST,(y,y))
    A[i]=k

DOUBLING=[A]
 
for i in range(60):
    X=[-1]*len(LIST)
 
    for j in range(len(LIST)):
        if DOUBLING[-1][j]==len(LIST):
            X[j]=len(LIST)
        else:
            X[j]=DOUBLING[-1][DOUBLING[-1][j]]
 
    DOUBLING.append(X)

ANS=1<<60

for x,y in LR:
    now=bisect(LIST,(y,y))

    b=K-2
    while b!=0 and now!=len(LIST):
        c=b.bit_length()-1
        now=DOUBLING[c][now]
        b^=1<<c

    if b==0 and now!=len(LIST):
        ANS=min(ANS,LIST[now][1]-x)

if ANS==1<<60:
    print(-1)
else:
    print(ANS)
0