結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    H = list(map(int, data[idx:idx+N]))
    idx += N
    T = list(map(int, data[idx:idx+N]))
    idx += N
    Q = int(data[idx])
    idx +=1
    queries = []
    for _ in range(Q):
        A = int(data[idx])-1  # convert to 0-based
        B = int(data[idx+1])-1
        idx +=2
        queries.append( (A, B) )
    
    # Precompute max_T for each j
    sorted_HT = sorted(zip(H, T), key=lambda x: x[0])
    h_list_sorted = [x[0] for x in sorted_HT]
    t_list_sorted = [x[1] for x in sorted_HT]
    # Compute prefix_max_T for all nodes
    prefix_max_T = []
    current_max = 0
    for t in t_list_sorted:
        current_max = max(current_max, t)
        prefix_max_T.append(current_max)
    
    # For each j, compute max_T_j
    max_T = [0]*N
    for j in range(N):
        t_j = T[j]
        idx_j = bisect.bisect_right(h_list_sorted, t_j) - 1
        if idx_j >=0:
            max_T[j] = prefix_max_T[idx_j]
        else:
            max_T[j] = 0
    
    # Create list of (H_j, T_j, max_T_j) and sort by H_j
    nodes = []
    for j in range(N):
        nodes.append( (H[j], T[j], max_T[j]) )
    nodes_sorted = sorted(nodes, key=lambda x: x[0])
    
    # Extract H, T, max_T from sorted nodes
    h_sorted = [x[0] for x in nodes_sorted]
    t_sorted = [x[1] for x in nodes_sorted]
    max_t_sorted = [x[2] for x in nodes_sorted]
    
    # Compute prefix_max_T_sorted and prefix_max_max_T_sorted
    prefix_max_T_sorted = []
    current_max = 0
    for t in t_sorted:
        current_max = max(current_max, t)
        prefix_max_T_sorted.append(current_max)
    
    prefix_max_max_T_sorted = []
    current_max = 0
    for mt in max_t_sorted:
        current_max = max(current_max, mt)
        prefix_max_max_T_sorted.append(current_max)
    
    # Process queries
    results = []
    for A, B in queries:
        h_b = H[B]
        t_a = T[A]
        if h_b <= t_a:
            results.append(1)
            continue
        else:
            # Find x = t_a in h_sorted
            idx_a = bisect.bisect_right(h_sorted, t_a) -1
            if idx_a <0:
                max_t = 0
                max_mt = 0
            else:
                max_t = prefix_max_T_sorted[idx_a]
                max_mt = prefix_max_max_T_sorted[idx_a]
            if max_t >= h_b:
                results.append(2)
            else:
                if max_mt >= h_b:
                    results.append(3)
                else:
                    results.append(-1)
    # Print results
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

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