結果

問題 No.2543 Many Meetings
ユーザー titiatitia
提出日時 2023-11-26 03:34:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,513 ms / 2,000 ms
コード長 1,286 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 224,456 KB
最終ジャッジ日時 2023-11-26 03:34:35
合計ジャッジ時間 30,950 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,460 KB
testcase_01 AC 42 ms
53,460 KB
testcase_02 AC 41 ms
53,460 KB
testcase_03 AC 1,376 ms
223,060 KB
testcase_04 AC 1,382 ms
221,564 KB
testcase_05 AC 1,383 ms
224,456 KB
testcase_06 AC 1,357 ms
222,208 KB
testcase_07 AC 1,359 ms
221,608 KB
testcase_08 AC 1,513 ms
220,432 KB
testcase_09 AC 1,459 ms
221,828 KB
testcase_10 AC 1,431 ms
220,820 KB
testcase_11 AC 1,402 ms
221,376 KB
testcase_12 AC 1,454 ms
221,620 KB
testcase_13 AC 1,173 ms
189,340 KB
testcase_14 AC 677 ms
137,724 KB
testcase_15 AC 596 ms
136,628 KB
testcase_16 AC 1,012 ms
174,564 KB
testcase_17 AC 1,112 ms
186,116 KB
testcase_18 AC 1,195 ms
192,128 KB
testcase_19 AC 1,091 ms
188,416 KB
testcase_20 AC 1,178 ms
187,008 KB
testcase_21 AC 1,302 ms
206,776 KB
testcase_22 AC 1,072 ms
186,156 KB
testcase_23 AC 73 ms
72,884 KB
testcase_24 AC 51 ms
64,036 KB
testcase_25 AC 57 ms
66,108 KB
testcase_26 AC 59 ms
66,376 KB
testcase_27 AC 75 ms
73,780 KB
testcase_28 AC 580 ms
102,968 KB
testcase_29 AC 232 ms
83,256 KB
testcase_30 AC 237 ms
83,520 KB
testcase_31 AC 76 ms
79,356 KB
testcase_32 AC 128 ms
88,808 KB
testcase_33 AC 40 ms
53,460 KB
testcase_34 AC 40 ms
53,460 KB
testcase_35 AC 40 ms
53,460 KB
testcase_36 AC 44 ms
53,460 KB
testcase_37 AC 40 ms
53,460 KB
testcase_38 AC 42 ms
53,460 KB
testcase_39 AC 41 ms
53,460 KB
testcase_40 AC 41 ms
53,460 KB
testcase_41 AC 40 ms
53,460 KB
testcase_42 AC 40 ms
53,460 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