外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

D - Gathering Nyans

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 300 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

ねこちゃんがいっぱい来てくれるVV は、Di≤V<SiD_i \leq V < S_i を満たす ii が一番多くなる VV です。 つまり、区間 [Di,Si)[D_i, S_i) が一番多く重なっている場所を求めればよいです。

ただし 1≤Di<Si≤1091 \leq D_i < S_i \leq 10^9 なので、座標ごとに数を持つ長さ 10910^9 の配列は作れません。 そこで、各区間の左端と右端だけをイベントとして持ち、座標順に並べて重なりの数を数えます(イベントソート)。

N = int(input())
E = []
for i in range(N):
    d, s = map(int,input().split())
    E.append((d, 0))
    E.append((s-1, 1))
E.sort()


coverd = 0
ans = -1
for i in range(2*N):
    e, f = E[i]
    if f == 0:
        coverd += 1
    else:
        coverd -= 1
    ans = max(coverd, ans)
print(ans)

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。