結果
| 問題 |
No.2242 Cities and Teleporters
|
| コンテスト | |
| ユーザー |
 neterukun
|
| 提出日時 | 2023-03-10 23:21:16 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,109 ms / 3,000 ms |
| コード長 | 7,158 bytes |
| コンパイル時間 | 214 ms |
| コンパイル使用メモリ | 82,004 KB |
| 実行使用メモリ | 263,776 KB |
| 最終ジャッジ日時 | 2024-09-18 05:37:14 |
| 合計ジャッジ時間 | 41,198 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.buffer.readline
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]
class Doubling:
def __init__(self, permutation, power=18):
self.n = len(permutation)
self.perm = permutation
self.power = power
self._build()
def _build(self):
self.next = [[0] * self.n for i in range(self.power)]
for v in range(self.n):
self.next[0][v] = self.perm[v]
for k in range(self.power - 1):
for v in range(self.n):
if self.next[k][v] == -1:
self.next[k + 1][v] = -1
continue
self.next[k + 1][v] = self.next[k][self.next[k][v]]
def build_path(self, values, op=max, e=-10**18):
self.op = op
self.e = e
self.data = [[e] * self.n for i in range(self.power)]
for v in range(self.n):
self.data[0][v] = self.op(self.e, values[v])
for k in range(self.power - 1):
for v in range(self.n):
if self.next[k][v] == -1:
self.data[k + 1][v] = e
continue
self.data[k + 1][v] = self.op(self.data[k][v],
self.data[k][self.next[k][v]])
def min_times(self, v, start, goal):
res = start
times = 1
for k in reversed(range(self.power)):
if self.next[k][v] == -1 or self.data[k][v] == -10**18:
continue
if self.op(res, self.data[k][v]) < goal:
res = self.op(res, self.data[k][v])
times += 1 << k
v = self.next[k][v]
if self.data[0][v] >= goal:
return times
else:
return -1
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]
db = Doubling(to)
db.build_path(tt, op=max, e=-10**18)
for u, v in queries:
u -= 1
v -= 1
print(db.min_times(index[t[u]], t[u], h[v]))