結果
問題 | No.1170 Never Want to Walk |
ユーザー | 草苺奶昔 |
提出日時 | 2023-02-14 22:23:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 547 ms / 2,000 ms |
コード長 | 3,435 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 87,120 KB |
実行使用メモリ | 120,152 KB |
最終ジャッジ日時 | 2023-09-24 09:28:22 |
合計ジャッジ時間 | 13,612 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 165 ms
80,660 KB |
testcase_01 | AC | 167 ms
80,664 KB |
testcase_02 | AC | 167 ms
80,496 KB |
testcase_03 | AC | 167 ms
80,664 KB |
testcase_04 | AC | 171 ms
80,696 KB |
testcase_05 | AC | 168 ms
80,668 KB |
testcase_06 | AC | 173 ms
80,672 KB |
testcase_07 | AC | 166 ms
80,340 KB |
testcase_08 | AC | 166 ms
80,328 KB |
testcase_09 | AC | 167 ms
80,704 KB |
testcase_10 | AC | 166 ms
80,692 KB |
testcase_11 | AC | 165 ms
80,668 KB |
testcase_12 | AC | 186 ms
82,116 KB |
testcase_13 | AC | 185 ms
82,108 KB |
testcase_14 | AC | 191 ms
81,696 KB |
testcase_15 | AC | 186 ms
81,752 KB |
testcase_16 | AC | 187 ms
82,356 KB |
testcase_17 | AC | 190 ms
82,400 KB |
testcase_18 | AC | 185 ms
82,208 KB |
testcase_19 | AC | 188 ms
82,296 KB |
testcase_20 | AC | 190 ms
82,160 KB |
testcase_21 | AC | 190 ms
82,068 KB |
testcase_22 | AC | 188 ms
82,196 KB |
testcase_23 | AC | 194 ms
81,908 KB |
testcase_24 | AC | 190 ms
82,012 KB |
testcase_25 | AC | 187 ms
82,080 KB |
testcase_26 | AC | 191 ms
82,140 KB |
testcase_27 | AC | 479 ms
119,056 KB |
testcase_28 | AC | 463 ms
118,792 KB |
testcase_29 | AC | 547 ms
119,576 KB |
testcase_30 | AC | 480 ms
119,168 KB |
testcase_31 | AC | 508 ms
118,812 KB |
testcase_32 | AC | 366 ms
119,016 KB |
testcase_33 | AC | 414 ms
119,360 KB |
testcase_34 | AC | 413 ms
119,424 KB |
testcase_35 | AC | 418 ms
119,560 KB |
testcase_36 | AC | 372 ms
119,484 KB |
testcase_37 | AC | 398 ms
119,280 KB |
testcase_38 | AC | 368 ms
120,152 KB |
ソースコード
# https://nyaannyaan.github.io/library/data-structure/range-union-find.hpp # 区间并查集 RangeUnionFind from bisect import bisect_left, bisect_right 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) -> bool: 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] return True def unionRange(self, start: int, end: int) -> 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) 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__": # uf = RangeUnionFind(10) # print(uf.unionRange(0, 5)) # print(uf.unionRange(0, 5)) # print(uf.isConnected(0, 4)) # print(uf.size(0)) # 2158. 每天绘制新区域的数量 # https://leetcode-cn.com/problems/amount-of-new-area-painted-each-day/ # 1 <= paint.length <= 1e5 # paint[i].length == 2 # 0 <= starti < endi <= 5 * 104 from typing import List class Solution: def amountPainted(self, paint: List[List[int]]) -> List[int]: uf = RangeUnionFind(int(5e4) + 10) res = [0] * len(paint) for i, (start, end) in enumerate(paint): res[i] = uf.unionRange(start, end + 1) return res # 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))