結果
問題 | No.1170 Never Want to Walk |
ユーザー | Kiri8128 |
提出日時 | 2020-08-16 17:05:03 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,951 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 506,620 KB |
最終ジャッジ日時 | 2024-04-19 18:24:54 |
合計ジャッジ時間 | 24,575 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
54,524 KB |
testcase_01 | AC | 38 ms
56,372 KB |
testcase_02 | AC | 38 ms
54,256 KB |
testcase_03 | AC | 37 ms
55,768 KB |
testcase_04 | AC | 38 ms
56,056 KB |
testcase_05 | AC | 37 ms
55,320 KB |
testcase_06 | AC | 37 ms
55,776 KB |
testcase_07 | AC | 38 ms
56,336 KB |
testcase_08 | AC | 37 ms
55,208 KB |
testcase_09 | AC | 37 ms
55,256 KB |
testcase_10 | AC | 38 ms
55,356 KB |
testcase_11 | AC | 37 ms
55,128 KB |
testcase_12 | AC | 81 ms
77,456 KB |
testcase_13 | AC | 85 ms
77,648 KB |
testcase_14 | AC | 89 ms
77,752 KB |
testcase_15 | AC | 77 ms
77,272 KB |
testcase_16 | AC | 82 ms
77,368 KB |
testcase_17 | AC | 94 ms
77,804 KB |
testcase_18 | AC | 79 ms
77,136 KB |
testcase_19 | AC | 82 ms
77,200 KB |
testcase_20 | AC | 93 ms
77,812 KB |
testcase_21 | AC | 82 ms
77,012 KB |
testcase_22 | AC | 102 ms
77,412 KB |
testcase_23 | AC | 103 ms
77,624 KB |
testcase_24 | AC | 103 ms
77,580 KB |
testcase_25 | AC | 103 ms
77,708 KB |
testcase_26 | AC | 104 ms
77,804 KB |
testcase_27 | AC | 1,291 ms
304,644 KB |
testcase_28 | AC | 1,254 ms
291,964 KB |
testcase_29 | AC | 1,178 ms
274,700 KB |
testcase_30 | AC | 1,236 ms
280,712 KB |
testcase_31 | AC | 1,221 ms
298,592 KB |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | AC | 1,945 ms
442,012 KB |
testcase_35 | TLE | - |
testcase_36 | AC | 1,934 ms
457,716 KB |
testcase_37 | AC | 1,977 ms
506,620 KB |
testcase_38 | AC | 1,884 ms
457,496 KB |
ソースコード
from bisect import bisect_right as br from collections import deque class range_edge: def __init__(self, n): self.k = (n-1).bit_length() self.K = 1 << self.k self.KK = self.K * 3 self.E = [[] for _ in range(self.KK)] for i in range(2, self.K * 2): self.E[i >> 1].append(i) for i in range(self.K, self.KK - 2): self.E[i].append(i + self.KK >> 1) self.c = self.KK # Number of Vertices def indices(self, l, r): l += self.K r += self.K while l < r: if l & 1: yield l l += 1 l >>= 1 if r & 1: r -= 1 yield r r >>= 1 def add_range_edge(self, a, b, c, d): # from [a, b) to [c, d) if a >= b or c >= d: return for i in self.indices(a - self.KK, b - self.KK): self.E[i + self.KK].append(self.c) self.c += 1 self.E.append([self.c]) # cost = 0 self.E.append([]) for i in self.indices(c, d): self.E[self.c].append(i) self.c += 1 def BFS0(self, i0=0): K = self.K i0 += K Q = deque([i0]) n = self.c done = {i0} while Q: i = Q.popleft() for j in self.E[i]: if j not in done: done.add(j) Q.append(j) return [a - K for a in done if K <= a < 2 * K] def debug(self): print("E =", self.E) N, A, B = map(int, input().split()) re = range_edge(N) X = [int(a) for a in input().split()] for i in range(N): l = br(X, X[i] + A - 1) r = br(X, X[i] + B) re.add_range_edge(i, i + 1, l, r) re.add_range_edge(l, r, i, i + 1) ANS = [0] * N for i in range(N): if ANS[i]: continue bfs = re.BFS0(i) ans = len(bfs) for j in bfs: ANS[j] = ans print(*ANS, sep = "\n")