結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 22:21:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 511 ms / 2,000 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 104,408 KB |
最終ジャッジ日時 | 2024-10-10 15:43:11 |
合計ジャッジ時間 | 8,328 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
from bisect import bisect, bisect_left import sys def input(): return sys.stdin.readline()[:-1] class UnionFind(): def __init__(self, size): self.table = [-1 for _ in range(size)] self.size = [1 for _ in range(size)] def find(self, x): while self.table[x] >= 0: if self.table[self.table[x]] >= 0: self.table[x] = self.table[self.table[x]] x = self.table[x] return x def unite(self, x, y): s1 = self.find(x) s2 = self.find(y) if s1 == s2: return False else: if self.table[s1] > self.table[s2]: self.table[s2] = s1 self.table[s1] -= 1 self.size[s1] += self.size[s2] self.size[s2] = 0 else: self.table[s1] = s2 self.table[s2] -= 1 self.size[s2] += self.size[s1] self.size[s1] = 0 return True def get_size(self, x): return self.size[self.find(x)] n, a, b = map(int, input().split()) x = list(map(int, input().split())) uf = UnionFind(n) rm = -1 for i in range(n): l = bisect_left(x, x[i]+a) r = bisect(x, x[i]+b) #print(l, r) if l == r or l == n: continue uf.unite(i, l) for j in range(max(l, rm), r-1): if uf.find(j) != uf.find(j+1): uf.unite(j, j+1) else: break rm = r-1 print(*[uf.get_size(i) for i in range(n)], sep="\n")