結果
問題 | No.1170 Never Want to Walk |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-29 22:48:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 458 ms / 2,000 ms |
コード長 | 2,934 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,072 KB |
実行使用メモリ | 120,016 KB |
最終ジャッジ日時 | 2023-10-21 12:27:04 |
合計ジャッジ時間 | 11,451 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 67 ms
67,560 KB |
testcase_01 | AC | 66 ms
67,456 KB |
testcase_02 | AC | 67 ms
67,560 KB |
testcase_03 | AC | 66 ms
65,748 KB |
testcase_04 | AC | 65 ms
65,756 KB |
testcase_05 | AC | 66 ms
65,748 KB |
testcase_06 | AC | 66 ms
65,564 KB |
testcase_07 | AC | 64 ms
67,544 KB |
testcase_08 | AC | 65 ms
65,728 KB |
testcase_09 | AC | 63 ms
65,732 KB |
testcase_10 | AC | 66 ms
65,744 KB |
testcase_11 | AC | 66 ms
65,740 KB |
testcase_12 | AC | 114 ms
76,584 KB |
testcase_13 | AC | 98 ms
77,032 KB |
testcase_14 | AC | 96 ms
76,668 KB |
testcase_15 | AC | 96 ms
77,044 KB |
testcase_16 | AC | 95 ms
76,992 KB |
testcase_17 | AC | 94 ms
76,984 KB |
testcase_18 | AC | 93 ms
77,000 KB |
testcase_19 | AC | 96 ms
77,000 KB |
testcase_20 | AC | 95 ms
77,012 KB |
testcase_21 | AC | 91 ms
76,996 KB |
testcase_22 | AC | 93 ms
76,980 KB |
testcase_23 | AC | 96 ms
77,044 KB |
testcase_24 | AC | 96 ms
77,028 KB |
testcase_25 | AC | 95 ms
76,988 KB |
testcase_26 | AC | 96 ms
77,032 KB |
testcase_27 | AC | 393 ms
118,540 KB |
testcase_28 | AC | 385 ms
119,120 KB |
testcase_29 | AC | 458 ms
119,572 KB |
testcase_30 | AC | 394 ms
119,544 KB |
testcase_31 | AC | 412 ms
119,120 KB |
testcase_32 | AC | 286 ms
119,880 KB |
testcase_33 | AC | 343 ms
119,168 KB |
testcase_34 | AC | 339 ms
119,540 KB |
testcase_35 | AC | 340 ms
120,016 KB |
testcase_36 | AC | 293 ms
119,292 KB |
testcase_37 | AC | 319 ms
119,220 KB |
testcase_38 | AC | 290 ms
119,304 KB |
ソースコード
from bisect import bisect_left, bisect_right from typing import Callable, Optional class RangeUnionFind: ___slots___ = ("_data", "_left", "_right") def __init__(self, n: int): self._data = [-1] * n self._left = list(range(n)) # 每个组的左边界 self._right = [i + 1 for i in range(n)] # 每个组的右边界 def find(self, x: int) -> int: if self._data[x] < 0: return x self._data[x] = self.find(self._data[x]) return self._data[x] def union(self, x: int, y: int, f: Optional[Callable[[int, int], None]] = None) -> bool: """ f: 合并时的回调函数,参数为合并后的根节点 (big, small) """ rootX = self.find(x) rootY = self.find(y) if rootX == rootY: return False if self._data[rootX] > self._data[rootY]: rootX, rootY = rootY, rootX self._data[rootX] += self._data[rootY] self._data[rootY] = rootX if self._left[rootY] < self._left[rootX]: self._left[rootX] = self._left[rootY] if self._right[rootY] > self._right[rootX]: self._right[rootX] = self._right[rootY] if f is not None: f(rootX, rootY) return True def unionRange( self, start: int, end: int, f: Optional[Callable[[int, int], None]] = None ) -> int: """合并`左闭右开区间[start, end)`,返回新合并的个数(次数)""" if start < 0: start = 0 if end > len(self._data): end = len(self._data) if start >= end: return 0 m, count = 0, 0 while True: m = self._right[self.find(start)] if m >= end: break self.union(start, m, f) count += 1 return count def isConnected(self, x: int, y: int) -> bool: return self.find(x) == self.find(y) def size(self, x: int) -> int: return -self._data[self.find(x)] if __name__ == "__main__": # No.1170 Never Want to Walk # https://yukicoder.me/problems/no/1170 # 数轴上有n个车站,第i个位置在xi # 如果两个车站之间的距离di与dj满足 A<=|di-dj|<=B,则这两个车站可以相互到达,否则不能相互到达 # 对每个车站,求出从该车站出发,可以到达的车站的数量 # 1<=n<=2e5 0<=A<=B<=1e9 0<=x1<=x2<...<=xn<=1e9 # !每个车站向右合并可以到达的车站,把合并分解为单点合并+区间合并 n, A, B = map(int, input().split()) pos = list(map(int, input().split())) uf = RangeUnionFind(n) for i, p in enumerate(pos): left = bisect_left(pos, p + A) right = bisect_right(pos, p + B) if left != right: # 有可以到达的车站 uf.union(i, left) uf.unionRange(left, right) for i in range(n): print(uf.size(i))