結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:29:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,365 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 193,732 KB
最終ジャッジ日時 2025-06-12 20:29:46
合計ジャッジ時間 13,327 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    # Preprocess max_T
    sorted_h = sorted(zip(H, T), key=lambda x: x[0])
    h_list = [x[0] for x in sorted_h]
    t_list = [x[1] for x in sorted_h]
    prefix_max = [0] * len(t_list)
    current_max = 0
    for i in range(len(t_list)):
        current_max = max(current_max, t_list[i])
        prefix_max[i] = current_max

    max_T = [0] * N
    for i in range(N):
        target = T[i]
        idx = bisect.bisect_right(h_list, target) - 1
        if idx >= 0:
            max_T[i] = prefix_max[idx]
        else:
            max_T[i] = 0  # Shouldn't happen per problem statement

    # Process queries
    results = []
    for A, B in queries:
        if H[B] <= T[A]:
            results.append(1)
        else:
            if H[B] <= max_T[A]:
                results.append(2)
            else:
                results.append(-1)

    print('\n'.join(map(str, results)))

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