コンテンツにスキップ

repovive starter round 10 C - Museum Records

サイト
repovive.com
コンテスト
repovive starter round 10
問題
C - Museum Records

nn 人が博物館に 1 回ずつ入って出ました。2n2n 回の入退場の時刻はすべて異なります。各人 ii について、

  • aia_i:ii が入る前に出ていた人数
  • bib_i:ii が出たあとに入ってきた人数

が記録されています。すべての記録が正しくなる入退場の順番があるか判定する問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤ai,bi<n0 \le a_i, b_i < n)。

aia_i は、入るのが遅い人ほど大きいか等しいです。よって、入る順番は aia_i の昇順です。aia_i が等しい人どうしの間では誰も出ていないので、その人たちの入る順番を入れ替えても、ほかの人の a,ba, b は変わりません。

kk 人目が入ってから k+1k + 1 人目が入るまでの間を「すき間 kk」と呼びます(すき間 nn は最後の人が入ったあと)。bib_i 人があとから入ってくるので、人 ii はすき間 n−bin - b_i で出ます。同じすき間で出る人どうしの順番は、記録に影響しません。

こうして入退場の順番は(記録に影響しない入れ替えを除いて)決まるので、次の 2 つを満たすか調べれば十分です。人 ii が kik_i 番目に入るとします。

  1. 入ってから出る:ki≤n−bik_i \le n - b_i。
  2. aia_i が正しい:aia_i は、n−bj≤ki−1n - b_j \le k_i - 1 である人 jj の人数に等しい。

aia_i が等しい人どうしの順番は 2. に影響しないので、1. を満たしやすい順にします。それは bib_i の大きい人(早く出る人)を先にする順です。

aia_i の昇順、同じなら bib_i の降順に並べます。0-indexed で ii 番目の人は k=i+1k = i + 1 番目に入るので、1. は i+1≤n−bi + 1 \le n - b です。

また、2. の人数は、すき間ごとに出る人数を数えて累積和をとれば求まります。ckc_k を「すき間 kk 以下で出る人数」とすると、2. は a=cia = c_i です。

全員がこの 2 つを満たせば Yes、そうでなければ No です。計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n = int(input())
ab = [tuple(map(int, input().split())) for i in range(n)]
ab.sort(key=lambda x: (x[0], -x[1]))
c = [0] * (n + 1)
for a, b in ab:
c[n - b] += 1
for i in range(n):
c[i + 1] += c[i]
for i, (a, b) in enumerate(ab):
if i + 1 > n - b or a != c[i]:
print("No")
exit(0)
print("Yes")