結果
問題 | No.2667 Constrained Permutation |
ユーザー | ゼット |
提出日時 | 2024-03-08 22:36:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 563 ms / 2,000 ms |
コード長 | 890 bytes |
コンパイル時間 | 397 ms |
コンパイル使用メモリ | 81,768 KB |
実行使用メモリ | 132,224 KB |
最終ジャッジ日時 | 2024-09-29 20:06:27 |
合計ジャッジ時間 | 13,012 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
N=int(input())l=0r=10**10L=[]R=[]h=[]u=10**10for i in range(N):a,b=map(int,input().split())L.append(a-1)R.append(b-1)h.append([a-1,b-1])u=min(u,a-1)L.sort()R.sort()for i in range(N):l=max(l,L[i]-i)for i in range(N):r=min(r,R[i]-i)if l>r:print(0)exit()ans=r-l+1if ans>10**2:print(ans)exit()p=0for i in range(N):h[i][0]-=uh[i][1]-=up=max(p,h[i][0])if p>10**7:print(ans)exit()G=[[] for i in range(p+1)]for i in range(N):x,y=h[i][:]G[x].append(y)result=0from heapq import heappush,heappopfor k in range(l-u,r-u+1):S=[]b=Truefor x in range(k):for y in G[x]:heappush(S,y)for i in range(N):t=i+kif t<=p:for y in G[t]:heappush(S,y)if len(S)==0:b=Falsebreakw=heappop(S)if w<t:b=Falsebreakif b==True:result+=1print(result)