結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:30:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,335 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 81,516 KB
実行使用メモリ 184,964 KB
最終ジャッジ日時 2025-06-12 20:31:58
合計ジャッジ時間 16,997 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    # Create sorted_towns: list of tuples (H_j, T_j, original_j)
    sorted_towns = []
    for i in range(N):
        sorted_towns.append((H[i], T[i], i))
    # Sort by H_j
    sorted_towns.sort(key=lambda x: x[0])
    
    # Precompute prefix_max, prefix_second_max, prefix_max_j, prefix_second_max_j
    len_st = len(sorted_towns)
    prefix_max = [0] * len_st
    prefix_second_max = [0] * len_st
    prefix_max_j = [0] * len_st
    prefix_second_max_j = [0] * len_st
    
    if len_st == 0:
        pass
    else:
        prefix_max[0] = sorted_towns[0][1]
        prefix_max_j[0] = 0
        prefix_second_max[0] = 0
        prefix_second_max_j[0] = -1
        
        for i in range(1, len_st):
            current_T = sorted_towns[i][1]
            prev_max = prefix_max[i-1]
            prev_second = prefix_second_max[i-1]
            
            if current_T > prev_max:
                prefix_max[i] = current_T
                prefix_max_j[i] = i
                prefix_second_max[i] = prev_max
                prefix_second_max_j[i] = prefix_max_j[i-1]
            elif current_T == prev_max:
                prefix_max[i] = current_T
                prefix_max_j[i] = i  # Update to current j
                prefix_second_max[i] = prev_second
                prefix_second_max_j[i] = prefix_second_max_j[i-1]
            else:
                if current_T > prev_second:
                    prefix_max[i] = prev_max
                    prefix_max_j[i] = prefix_max_j[i-1]
                    prefix_second_max[i] = current_T
                    prefix_second_max_j[i] = i
                else:
                    prefix_max[i] = prev_max
                    prefix_max_j[i] = prefix_max_j[i-1]
                    prefix_second_max[i] = prev_second
                    prefix_second_max_j[i] = prefix_second_max_j[i-1]
    
    Q = int(data[ptr])
    ptr += 1
    
    for _ in range(Q):
        A = int(data[ptr]) - 1
        B = int(data[ptr+1]) - 1
        ptr += 2
        
        h_b = H[B]
        t_a = T[A]
        
        if h_b <= t_a:
            print(1)
            continue
        
        x = t_a
        
        # Binary search to find best in sorted_towns
        left = 0
        right = len(sorted_towns) - 1
        best = -1
        while left <= right:
            mid = (left + right) // 2
            if sorted_towns[mid][0] <= x:
                best = mid
                left = mid + 1
            else:
                right = mid - 1
        
        if best == -1:
            print(-1)
            continue
        
        max_T = prefix_max[best]
        if max_T < h_b:
            print(-1)
            continue
        
        max_j_in_sorted = prefix_max_j[best]
        original_j = sorted_towns[max_j_in_sorted][2]
        
        if original_j != A:
            print(2)
            continue
        else:
            second_max_T = prefix_second_max[best]
            if second_max_T >= h_b:
                print(2)
            else:
                print(-1)

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