結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:11:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,466 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 53,944 KB
最終ジャッジ日時 2025-04-15 22:12:39
合計ジャッジ時間 6,726 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    H = list(map(int, input[ptr:ptr+N]))
    ptr += N
    T = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    queries = []
    for _ in range(Q):
        A = int(input[ptr])-1
        B = int(input[ptr+1])-1
        queries.append((A, B))
        ptr += 2

    sorted_h = sorted(zip(H, T), key=lambda x: x[0])
    H_sorted = [x[0] for x in sorted_h]
    T_sorted = [x[1] for x in sorted_h]

    max1 = []
    count_max = []
    max2 = []
    current_max = -float('inf')
    current_count = 0
    current_max2 = -float('inf')

    for t in T_sorted:
        if t > current_max:
            current_max2 = current_max
            current_max = t
            current_count = 1
        elif t == current_max:
            current_count += 1
        else:
            if t > current_max2:
                current_max2 = t
        max1.append(current_max)
        count_max.append(current_count)
        max2.append(current_max2)

    for A, B in queries:
        H_B = H[B]
        T_A = T[A]
        if H_B <= T_A:
            print(1)
            continue

        i = bisect.bisect_right(H_sorted, T_A) - 1
        if i < 0:
            print(-1)
            continue

        max_all = max1[i]
        count = count_max[i]
        if H[A] <= T_A:
            if T[A] == max_all:
                if count > 1:
                    new_max = max_all
                else:
                    new_max = max2[i] if i >= 0 else -float('inf')
            else:
                new_max = max_all
        else:
            new_max = max_all

        if new_max <= T_A:
            print(-1)
            continue

        current_max_val = new_max
        step_count = 1
        if current_max_val >= H_B:
            print(2)
            continue

        while True:
            i_new = bisect.bisect_right(H_sorted, current_max_val) - 1
            if i_new < 0:
                new_max_val = -float('inf')
            else:
                new_max_val = max1[i_new]

            if new_max_val == current_max_val:
                break
            step_count += 1
            current_max_val = new_max_val
            if current_max_val >= H_B:
                break

        if current_max_val >= H_B:
            print(step_count + 1)
        else:
            print(-1)

if __name__ == "__main__":
    main()
0