結果

問題 No.2242 Cities and Teleporters
ユーザー gew1fw
提出日時 2025-06-12 20:32:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,484 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 81,940 KB
実行使用メモリ 239,708 KB
最終ジャッジ日時 2025-06-12 20:34:05
合計ジャッジ時間 22,410 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 7 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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])
        B = int(data[ptr+1])
        queries.append((A-1, B-1))  # convert to 0-based
        ptr += 2
    
    # Preprocess
    cities = list(zip(H, T, range(N)))
    cities.sort()
    prefix_max = []
    max_so_far = -1
    for h, t, idx in cities:
        if t > max_so_far:
            max_so_far = t
        prefix_max.append(max_so_far)
    
    # Precompute M for each city
    max_steps = 20
    M = []
    for i in range(N):
        h_i = H[i]
        t_i = T[i]
        current_M = [t_i]
        current_T = t_i
        for _ in range(max_steps):
            x = current_T
            # find the index where cities[j].H <= x, find the largest j
            low = 0
            high = N - 1
            res = -1
            while low <= high:
                mid = (low + high) // 2
                if cities[mid][0] <= x:
                    res = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if res == -1:
                max_t = current_T
            else:
                max_t = prefix_max[res]
            if max_t == current_T:
                current_M.append(max_t)
                break
            else:
                current_M.append(max_t)
                current_T = max_t
        # Pad to max_steps+1 if necessary
        while len(current_M) <= max_steps:
            current_M.append(current_M[-1])
        M.append(current_M[:max_steps + 1])
    
    # Process queries
    output = []
    for a, b in queries:
        target = H[b]
        ma_list = M[a]
        max_m = ma_list[-1]
        if target > max_m:
            output.append("-1")
            continue
        # Find the smallest k where ma_list[k-1] >= target
        found = False
        for k in range(1, len(ma_list) + 1):
            if k-1 >= len(ma_list):
                m = max_m
            else:
                m = ma_list[k-1]
            if m >= target:
                output.append(str(k))
                found = True
                break
        if not found:
            output.append("-1")
    print('\n'.join(output))

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