結果

問題 No.2242 Cities and Teleporters
ユーザー neterukunneterukun
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
53,760 KB
testcase_01 AC 36 ms
53,632 KB
testcase_02 AC 37 ms
54,052 KB
testcase_03 AC 39 ms
53,632 KB
testcase_04 AC 37 ms
54,032 KB
testcase_05 AC 1,898 ms
260,604 KB
testcase_06 AC 1,596 ms
263,776 KB
testcase_07 AC 1,934 ms
260,836 KB
testcase_08 AC 2,095 ms
261,128 KB
testcase_09 AC 1,791 ms
261,128 KB
testcase_10 AC 1,459 ms
260,948 KB
testcase_11 AC 1,817 ms
261,152 KB
testcase_12 AC 1,734 ms
260,792 KB
testcase_13 AC 1,944 ms
261,312 KB
testcase_14 AC 2,109 ms
261,252 KB
testcase_15 AC 2,014 ms
260,984 KB
testcase_16 AC 1,940 ms
261,196 KB
testcase_17 AC 1,945 ms
261,320 KB
testcase_18 AC 1,844 ms
260,412 KB
testcase_19 AC 1,661 ms
261,100 KB
testcase_20 AC 1,798 ms
260,656 KB
testcase_21 AC 1,993 ms
260,480 KB
testcase_22 AC 1,603 ms
260,356 KB
testcase_23 AC 1,587 ms
261,224 KB
testcase_24 AC 1,641 ms
260,676 KB
testcase_25 AC 1,641 ms
261,268 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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