結果

問題 No.2242 Cities and Teleporters
ユーザー tassei903
提出日時 2025-04-11 15:37:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,403 ms / 3,000 ms
コード長 1,643 bytes
コンパイル時間 662 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 183,680 KB
最終ジャッジ日時 2025-04-11 15:37:52
合計ジャッジ時間 27,077 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

n = ni()
h = na()
t = na()
idx = sorted(range(n), key = lambda x:h[x])
idx_inv = [-1] * n
for i in range(n):
    idx_inv[idx[i]] = i
h = [h[idx[i]] for i in range(n)]
t = [t[idx[i]] for i in range(n)]

q = ni()
a, b = zip(*[na() for i in range(q)])
a = [idx_inv[a[i]-1] for i in range(q)]
b = [idx_inv[b[i]-1] for i in range(q)]

tt = list(t)
for i in range(n-1):
    tt[i+1] = max(tt[i], tt[i+1])

# print(h)
# print(t)
# print(tt)

B = 20
doubling = [[-1] * n for i in range(B)]
from bisect import bisect_right
for i in range(n):
    doubling[0][i] = bisect_right(h, tt[i]) - 1
one = [-1] * n
for i in range(n):
    one[i] = bisect_right(h, t[i]) - 1
for i in range(B-1):
    for j in range(n):
        if doubling[i][j] != -1:
            doubling[i+1][j] = doubling[i][doubling[i][j]]
    
# for i in range(B):
#     print(*doubling[i])

# print(one)
for i in range(q):
    x, y = a[i], b[i]
    # print(x, y)
    if t[x] >= h[y]:
        print(1)
    elif one[x] == -1:
        print(-1)
    else:
        x = one[x]
        if doubling[-1][x] < y:
            print(-1)
        else:
            ans = 0
            for i in range(B-1, -1, -1):
                if doubling[i][x] < y:
                    x = doubling[i][x]
                    ans += 1 << i
            print(ans + 2)
0