結果

問題 No.2543 Many Meetings
ユーザー titia
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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