結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー norioc
提出日時 2026-05-04 04:21:15
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,973 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 339 ms
コンパイル使用メモリ 85,760 KB
実行使用メモリ 173,412 KB
最終ジャッジ日時 2026-05-04 04:22:03
合計ジャッジ時間 15,702 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 3 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline


class Doubling:
    def __init__(self, xs: list, nb=21):
        size = len(xs)
        doubling = [[0] * size for _ in range(nb)]
        for i in range(size):
            doubling[0][i] = xs[i]

        for k in range(nb-1):
            for i in range(size):
                doubling[k+1][i] = doubling[k][doubling[k][i]]

        self.nb = nb
        self.doubling = doubling

    def query(self, k: int, start: int) -> int:
        cur = start
        for i in range(self.nb):
            if k & (1 << i):
                cur = self.doubling[i][cur]

        return cur


from bisect import bisect_right
from itertools import accumulate

N = int(input())
H = list(map(int, input().split()))
T = list(map(int, input().split()))
Q = int(input())

cities = [(h, t, i) for i, (h, t) in enumerate(zip(H, T))]
cities.sort()

acc = list(accumulate([(t, i) for _, t, i in cities], func=max))
# print(f'{acc=}')
# exit()

nexts = []
for i in range(N):
    # 街 i の次への遷移を求める
    # テレポート可能な街のうち、最も h の高い街を求める
    p = bisect_right(cities, T[i], key=lambda x: x[0])
    if p == 0:  # どこにも移動出来ない
        nexts.append(i)
    else:
        # t, ci = segt.prod(0, p)
        t, ci = acc[p-1]
        if t > T[i]:
            nexts.append(ci)  # テレポートするとより高く移動できる
        else:
            nexts.append(i)  # 現状より高い位置に移動出来ない

d = Doubling(nexts)
for _ in range(Q):
    A, B = map(lambda x: int(x)-1, input().split())

    k = 2 * 10**5
    ci = d.query(k, A)

    # 街 B の高さに届かない
    if H[B] > T[ci]:
        print(-1)
        continue

    lo = 0
    hi = k
    res = k
    while lo <= hi:
        m = (lo + hi) // 2
        ci = d.query(m, A)
        if T[ci] >= H[B]:
            res = min(res, m)
            hi = m - 1
        else:
            lo = m + 1

    print(res+1)
0