結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー neterukun
提出日時 2023-03-10 22:54:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,633 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 270,828 KB
最終ジャッジ日時 2024-09-18 05:02:40
合計ジャッジ時間 6,348 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]]]
0