結果

問題 No.2242 Cities and Teleporters
ユーザー neterukunneterukun
提出日時 2023-03-10 23:19:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 7,114 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 353,592 KB
最終ジャッジ日時 2024-09-18 05:32:03
合計ジャッジ時間 63,772 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
53,888 KB
testcase_01 AC 42 ms
54,144 KB
testcase_02 AC 42 ms
54,528 KB
testcase_03 AC 42 ms
54,400 KB
testcase_04 AC 46 ms
59,776 KB
testcase_05 TLE -
testcase_06 AC 2,719 ms
346,156 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 2,126 ms
345,088 KB
testcase_11 AC 2,800 ms
351,340 KB
testcase_12 AC 2,806 ms
353,592 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 AC 2,860 ms
346,212 KB
testcase_19 AC 2,721 ms
344,164 KB
testcase_20 AC 2,942 ms
335,200 KB
testcase_21 AC 2,867 ms
338,156 KB
testcase_22 AC 2,618 ms
341,644 KB
testcase_23 AC 2,503 ms
347,704 KB
testcase_24 AC 2,679 ms
348,032 KB
testcase_25 AC 2,698 ms
349,880 KB
権限があれば一括ダウンロードができます

ソースコード

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]


class Doubling:
    def __init__(self, permutation, power=64):
        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