結果
問題 | No.1170 Never Want to Walk |
ユーザー | 草苺奶昔 |
提出日時 | 2023-02-14 22:20:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 547 ms / 2,000 ms |
コード長 | 3,305 bytes |
コンパイル時間 | 688 ms |
コンパイル使用メモリ | 87,284 KB |
実行使用メモリ | 119,852 KB |
最終ジャッジ日時 | 2023-09-24 09:26:44 |
合計ジャッジ時間 | 13,268 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 170 ms
80,824 KB |
testcase_01 | AC | 173 ms
80,788 KB |
testcase_02 | AC | 173 ms
80,548 KB |
testcase_03 | AC | 174 ms
80,564 KB |
testcase_04 | AC | 173 ms
80,796 KB |
testcase_05 | AC | 174 ms
80,688 KB |
testcase_06 | AC | 172 ms
80,448 KB |
testcase_07 | AC | 174 ms
80,840 KB |
testcase_08 | AC | 176 ms
80,472 KB |
testcase_09 | AC | 178 ms
80,836 KB |
testcase_10 | AC | 173 ms
80,488 KB |
testcase_11 | AC | 170 ms
80,724 KB |
testcase_12 | AC | 194 ms
82,252 KB |
testcase_13 | AC | 193 ms
82,076 KB |
testcase_14 | AC | 203 ms
81,928 KB |
testcase_15 | AC | 199 ms
82,292 KB |
testcase_16 | AC | 201 ms
82,244 KB |
testcase_17 | AC | 200 ms
82,248 KB |
testcase_18 | AC | 196 ms
82,196 KB |
testcase_19 | AC | 200 ms
82,072 KB |
testcase_20 | AC | 200 ms
82,172 KB |
testcase_21 | AC | 201 ms
82,080 KB |
testcase_22 | AC | 198 ms
82,108 KB |
testcase_23 | AC | 203 ms
82,304 KB |
testcase_24 | AC | 197 ms
82,216 KB |
testcase_25 | AC | 196 ms
82,116 KB |
testcase_26 | AC | 202 ms
82,300 KB |
testcase_27 | AC | 491 ms
119,576 KB |
testcase_28 | AC | 467 ms
118,848 KB |
testcase_29 | AC | 547 ms
119,564 KB |
testcase_30 | AC | 489 ms
119,808 KB |
testcase_31 | AC | 508 ms
119,092 KB |
testcase_32 | AC | 362 ms
119,168 KB |
testcase_33 | AC | 422 ms
119,236 KB |
testcase_34 | AC | 424 ms
119,752 KB |
testcase_35 | AC | 425 ms
119,748 KB |
testcase_36 | AC | 379 ms
119,544 KB |
testcase_37 | AC | 409 ms
119,760 KB |
testcase_38 | AC | 379 ms
119,852 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))