結果
問題 | No.2667 Constrained Permutation |
ユーザー |
👑 |
提出日時 | 2024-03-08 21:58:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 463 ms / 2,000 ms |
コード長 | 752 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 81,952 KB |
実行使用メモリ | 119,268 KB |
最終ジャッジ日時 | 2024-09-29 19:37:44 |
合計ジャッジ時間 | 12,155 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
from heapq import * n = int(input()) L = [0] * n R = [0] * n for i in range(n): L[i], R[i] = map(int, input().split()) R_ = sorted(R) ma = min(r - i for i, r in enumerate(R_)) L_ = sorted(L) mi = max(l - i for i, l in enumerate(L_)) def ok(x): for i in range(n): L[i] -= x R[i] -= x L[i] = max(L[i], 0) R[i] = min(R[i], n - 1) add = [[] for _ in range(n)] for l, r in zip(L, R): add[l].append(r) hq = [] for i in range(n): for x in add[i]: heappush(hq, x) while hq and hq[0] < i: heappop(hq) if not hq: return False heappop(hq) return True if mi <= ma and ok(ma): print(ma - mi + 1) else: print(0)