結果
問題 | No.1170 Never Want to Walk |
ユーザー |
👑 ![]() |
提出日時 | 2020-08-15 16:50:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 478 ms / 2,000 ms |
コード長 | 3,479 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 82,140 KB |
実行使用メモリ | 105,468 KB |
最終ジャッジ日時 | 2024-10-10 18:12:10 |
合計ジャッジ時間 | 8,383 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
def Binary_Search_Small_Count(A,x,equal=False,sort=False):"""2分探索によって,x未満の要素の個数を調べる.A:リストx:調べる要素sort:ソートをする必要があるかどうか(Trueで必要)equal:Trueのときはx"未満"がx"以下"になる"""if sort:A.sort()N=len(A)if A[-1]<x:return Nelif x<A[0] or (not equal and x==A[0]):return 0L,R=0,Nwhile R-L>1:C=L+(R-L)//2if x<A[C] or (not equal and x==A[C]):R=Celse:L=Creturn R#------------------------------------------------class Union_Find():def __init__(self,N):"""0,1,...,n-1を要素として初期化する.n:要素数"""self.n=Nself.parents=[-1]*Nself.rank=[0]*Ndef find(self, x):"""要素xの属している族を調べる.x:要素"""if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):"""要素x,yを同一視する.x,y:要素"""x = self.find(x)y = self.find(y)if x == y:returnif self.rank[x]>self.rank[y]:self.parents[x] += self.parents[y]self.parents[y] = xelse:self.parents[y] += self.parents[x]self.parents[x] = yif self.rank[x]==self.rank[y]:self.rank[y]+=1def size(self, x):"""要素xの属している要素の数.x:要素"""return -self.parents[self.find(x)]def same(self, x, y):"""要素x,yは同一視されているか?x,y:要素"""return self.find(x) == self.find(y)def members(self, x):"""要素xが属している族の要素.※族の要素の個数が欲しいときはsizeを使うこと!!x:要素"""root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):"""族の名前のリスト"""return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):"""族の個数"""return len(self.roots())def all_group_members(self):"""全ての族の出力"""return {r: self.members(r) for r in self.roots()}def __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())class Imos_1:def __init__(self,N):self.len=Nself.list=[0]*(N+1)def Add(self,F,T,C=1):self.list[F]+=Cself.list[T+1]-=Cdef Cumulative_Sum(self):Y=[0]*(self.len)S=0for i in range(self.len):S+=self.list[i]Y[i]=Sreturn Y#================================================N,A,B=map(int,input().split())X=list(map(int,input().split()))U=Union_Find(N)I=Imos_1(N)for i in range(N):p=Binary_Search_Small_Count(X,X[i]+A)q=Binary_Search_Small_Count(X,X[i]+B,True)if p<N and p<q:U.union(i,p)if p<=q-2:I.Add(p,q-2)assert 1J=I.Cumulative_Sum()for i in range(N):if J[i]>0:U.union(i,i+1)X=[0]*Nfor i in range(N):X[i]=U.size(i)print("\n".join(map(str,X)))