結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 21:48:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 548 ms / 2,000 ms |
コード長 | 1,669 bytes |
コンパイル時間 | 448 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 105,892 KB |
最終ジャッジ日時 | 2024-10-10 14:56:47 |
合計ジャッジ時間 | 9,578 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys from bisect import bisect_left input = sys.stdin.readline class UnionFind(): def __init__(self, n): self.n = n self.root = [-1] * (n + 1) self.rnk = [0] * (n + 1) def find_root(self, x): while self.root[x] >= 0: x = self.root[x] return x def unite(self, x, y): x = self.find_root(x) y = self.find_root(y) if x == y: return elif self.rnk[x] > self.rnk[y]: self.root[x] += self.root[y] self.root[y] = x else: self.root[y] += self.root[x] self.root[x] = y if self.rnk[x] == self.rnk[y]: self.rnk[y] += 1 def isSameGroup(self, x, y): return self.find_root(x) == self.find_root(y) def size(self, x): return -self.root[self.find_root(x)] N, A, B = map(int, input().split()) X = list(map(int, input().split())) UF = UnionFind(N) imos = [0] * (N+1) for i in range(N): x = X[i] j0 = bisect_left(X, x+A) j1 = bisect_left(X, x+B+1) - 1 if i < j0 <= j1 < N: UF.unite(i + 1, j0 + 1) UF.unite(i+1, j1+1) if j0+1 < j1: imos[j0+1] += 1 imos[j1] -= 1 val = 0 for i in range(N): val += imos[i] if val > 0: UF.unite(i, i+1) UF.unite(i+1, i+2) for i in range(1, N+1): print(UF.size(i)) if __name__ == '__main__': main()