結果
| 問題 | No.2242 Cities and Teleporters |
| ユーザー |
 neterukun
|
| 提出日時 | 2023-03-10 22:54:33 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,633 bytes |
| コンパイル時間 | 1,713 ms |
| コンパイル使用メモリ | 81,496 KB |
| 実行使用メモリ | 267,544 KB |
| 最終ジャッジ日時 | 2023-10-18 08:35:50 |
| 合計ジャッジ時間 | 7,648 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
55,624 KB |
| testcase_01 | AC | 42 ms
55,496 KB |
| testcase_02 | AC | 42 ms
55,496 KB |
| testcase_03 | AC | 41 ms
55,496 KB |
| testcase_04 | AC | 42 ms
55,496 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
ソースコード
from bisect import bisect_left, bisect_right
class BitVector:
def __init__(self, n):
# self.BLOCK_WIDTH = 32
self.BLOCK_NUM = (n + 31) >> 5
self.bit = [0] * self.BLOCK_NUM
self.count = [0] * self.BLOCK_NUM
def _popcount(self, x):
x = x - ((x >> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
x = (x + (x >> 4)) & 0x0F0F0F0F
x = x + (x >> 8)
x = x + (x >> 16)
return x & 0x0000007F
def set(self, i):
self.bit[i >> 5] |= 1 << (i & 31)
def access(self, i):
return (self.bit[i >> 5] >> (i & 31)) & 1
def build(self):
for i in range(self.BLOCK_NUM - 1):
self.count[i + 1] = self.count[i] + self._popcount(self.bit[i])
def rank(self, r, f):
res = self.count[r >> 5] + self._popcount(self.bit[r >> 5] & ((1 << (r & 31)) - 1))
return res if f else r - res
class WaveletMatrix:
def __init__(self, array, MAXLOG=32):
self.MAXLOG = MAXLOG
self.n = len(array)
self.mat = []
self.mid = []
for d in reversed(range(self.MAXLOG)):
vec = BitVector(self.n + 1)
ls = []
rs = []
for i, val in enumerate(array):
if (val >> d) & 1:
rs.append(val)
vec.set(i)
else:
ls.append(val)
vec.build()
self.mat.append(vec)
self.mid.append(len(ls))
array = ls + rs
def access(self, i):
res = 0
for d in range(self.MAXLOG):
res <<= 1
if self.mat[d][i]:
res |= 1
i = self.mat[d].rank(i, 1) + self.mid[d]
else:
i = self.mat[d].rank(i, 0)
return res
def rank(self, l, r, val):
for d in range(self.MAXLOG):
if val >> (self.MAXLOG - d - 1) & 1:
l = self.mat[d].rank(l, 1) + self.mid[d]
r = self.mat[d].rank(r, 1) + self.mid[d]
else:
l = self.mat[d].rank(l, 0)
r = self.mat[d].rank(r, 0)
return r - l
def quantile(self, l, r, k):
res = 0
for d in range(self.MAXLOG):
res <<= 1
cntl, cntr = self.mat[d].rank(l, 0), self.mat[d].rank(r, 0)
if k >= cntr - cntl:
l = self.mat[d].rank(l, 1) + self.mid[d]
r = self.mat[d].rank(r, 1) + self.mid[d]
res |= 1
k -= cntr - cntl
else:
l = cntl
r = cntr
return res
def kth_smallest(self, l, r, k):
return self.quantile(l, r, k)
def kth_largest(self, l, r, k):
return self.quantile(l, r, r - l - k - 1)
def range_freq(self, l, r, upper):
res = 0
for d in range(self.MAXLOG):
if upper >> (self.MAXLOG - d - 1) & 1:
res += self.mat[d].rank(r, 0) - self.mat[d].rank(l, 0)
l = self.mat[d].rank(l, 1) + self.mid[d]
r = self.mat[d].rank(r, 1) + self.mid[d]
else:
l = self.mat[d].rank(l, 0)
r = self.mat[d].rank(r, 0)
return res
def prev_val(self, l, r, upper):
cnt = self.range_freq(l, r, upper)
return None if cnt == 0 else self.kth_smallest(l, r, cnt - 1)
def next_val(self, l, r, lower):
cnt = self.range_freq(l, r, lower)
return None if cnt == r - l else self.kth_smallest(l, r, cnt)
class CompressedWaveletMatrix:
def __init__(self, array):
self.vals = sorted(set(array))
self.comp = {val: idx for idx, val in enumerate(self.vals)}
array = [self.comp[val] for val in array]
MAXLOG = len(self.vals).bit_length()
self.wm = WaveletMatrix(array, MAXLOG)
def access(self, i):
return self.vals[self.wm.access(i)]
def rank(self, l, r, val):
return self.wm.rank(l, r, self.comp[val]) if val in self.comp else 0
def kth_smallest(self, l, r, k):
return self.vals[self.wm.kth_smallest(l, r, k)]
def kth_largest(self, l, r, k):
return self.vals[self.wm.kth_largest(l, r, k)]
def range_freq(self, l, r, upper):
upper = bisect_left(self.vals, upper)
return self.wm.range_freq(l, r, upper)
def prev_val(self, l, r, upper):
upper = bisect_left(self.vals, upper)
res = self.wm.prev_val(l, r, upper)
return None if res is None else self.vals[res]
def next_val(self, l, r, lower):
lower = bisect_left(self.vals, lower)
res = self.wm.next_val(l, r, lower)
return None if res is None else self.vals[res]
n = int(input())
h = list(map(int, input().split()))
t = list(map(int, input().split()))
q = int(input())
queries = [list(map(int, input().split())) for _ in range(q)]
ht = [(hv, tv) for hv, tv in zip(h, t)]
ht.sort()
hh = [hh for hh, _ in ht]
cwm = CompressedWaveletMatrix([tt for _, tt in ht])
tt = sorted(set(t))
to = [-1] * len(tt)
index = {val: i for i, val in enumerate(tt)}
for tv in tt:
r = bisect_right(hh, tv)
max_tv = cwm.kth_largest(0, r, 0)
if tv < max_tv:
to[index[tv]] = index[max_tv]
for u, v in queries:
u -= 1
v -= 1
t_u = t[u]
h_v = h[v]
cnt = 0
while True:
# これをダブリングする
if h_v <= t_u:
print(cnt + 1)
break
cnt += 1
if to[index[t_u]] == -1:
print(-1)
break
t_u = tt[to[index[t_u]]]