結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 21:48:33 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 728 ms / 2,000 ms |
コード長 | 1,974 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 32,704 KB |
最終ジャッジ日時 | 2024-10-10 14:56:24 |
合計ジャッジ時間 | 11,816 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
import sysreadline = sys.stdin.readlinereadall = sys.stdin.readns = lambda: readline().rstrip()ni = lambda: int(readline().rstrip())nm = lambda: map(int, readline().split())nl = lambda: list(map(int, readline().split()))prn = lambda x: print(*x, sep='\n')class UnionFind:def __init__(self, n):self.ps = [-1] * (n + 1)def find(self, x):if self.ps[x] < 0:return xelse:self.ps[x] = self.find(self.ps[x])return self.ps[x]def unite(self, x, y):x = self.find(x)y = self.find(y)if x == y:return Falseif self.ps[x] > self.ps[y]:x, y = y, xself.ps[x] += self.ps[y]self.ps[y] = xreturn Truedef same(self, x, y):return self.find(x) == self.find(y)def size(self, x):x = self.find(x)return -self.ps[x]def solve():n, a, b = nm()l = nl()uf = UnionFind(n)cur = -1lef, rig = 0, 0for i in range(n):while lef < n and l[lef] - l[i] < a:lef += 1while rig + 1 < n and l[rig + 1] - l[i] <= b:rig += 1for j in range(max(cur, lef), rig):uf.unite(j, j+1)# print('a', j, j+1)cur = rigif lef <= rig:uf.unite(i, lef)# print('b', i, lef)uf.unite(i, rig)# print('b', i, rig)# print(i, lef, rig)# cur = n# lef, rig = n-1, n-1# for i in range(n-1, -1, -1):# while rig >= 0 and l[i] - l[rig] < a:# rig -= 1# while lef > 0 and l[i] - l[lef-1] <= b:# lef -= 1# for j in range(min(cur, rig), lef):# uf.unite(j, j-1)# cur = lef# if rig >= 0:# uf.unite(i, lef)# uf.unite(i, rig)# print(i, lef, rig)for i in range(n):print(uf.size(i))returnsolve()