結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:03:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,002 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 198,184 KB
最終ジャッジ日時 2025-06-12 18:03:16
合計ジャッジ時間 6,162 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [-float('inf')] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])
    
    def query(self, l, r):
        res = -float('inf')
        if l > r:
            return res
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = max(res, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    import sys
    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
    
    # Preprocess sorted list and segment tree
    sorted_list = sorted( [ (i, H[i], T[i]) for i in range(N) ], key=lambda x: x[1] )
    sorted_h = [x[1] for x in sorted_list]
    sorted_t = [x[2] for x in sorted_list]
    st = SegmentTree(sorted_t)
    pos = [0]*N
    for i in range(N):
        original_index = sorted_list[i][0]
        pos[original_index] = i
    
    # Process each query
    for A_orig, B_orig in queries:
        H_B = H[B_orig]
        T_A = T[A_orig]
        if H_B <= T_A:
            print(1)
            continue
        
        # Compute maximum current_max for A_orig
        current_max = T_A
        while True:
            # Compute next_max
            X = current_max
            i = bisect.bisect_right(sorted_h, X) -1
            if i <0:
                next_max = -float('inf')
            else:
                pos_A = pos[A_orig]
                if sorted_list[pos_A][1] > X:
                    next_max = st.query(0, i)
                else:
                    if pos_A > i:
                        next_max = st.query(0, i)
                    else:
                        left = st.query(0, pos_A-1) if pos_A >0 else -float('inf')
                        right = st.query(pos_A+1, i) if (pos_A+1) <=i else -float('inf')
                        next_max = max(left, right)
            if next_max > current_max:
                current_max = next_max
            else:
                break
        
        if current_max < H_B:
            print(-1)
            continue
        
        # Compute steps_needed
        steps = 0
        current_max = T_A
        if current_max >= H_B:
            steps_needed = 0
        else:
            while True:
                X = current_max
                i = bisect.bisect_right(sorted_h, X) -1
                if i <0:
                    next_max = -float('inf')
                else:
                    pos_A = pos[A_orig]
                    if sorted_list[pos_A][1] > X:
                        next_max = st.query(0, i)
                    else:
                        if pos_A > i:
                            next_max = st.query(0, i)
                        else:
                            left = st.query(0, pos_A-1) if pos_A >0 else -float('inf')
                            right = st.query(pos_A+1, i) if (pos_A+1) <=i else -float('inf')
                            next_max = max(left, right)
                if next_max <= current_max:
                    break
                steps +=1
                current_max = next_max
                if current_max >= H_B:
                    break
        
        if current_max >= H_B:
            print(steps +1)
        else:
            print(-1)

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