結果

問題 No.2242 Cities and Teleporters
ユーザー gew1fw
提出日時 2025-06-12 18:04:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,259 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 203,940 KB
最終ジャッジ日時 2025-06-12 18:05:56
合計ジャッジ時間 20,571 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    # Prepare sorted_H and pos_in_sorted_H
    sorted_H = []
    for i in range(N):
        sorted_H.append((H[i], T[i], i))
    sorted_H.sort(key=lambda x: x[0])
    H_list = [h for h, t, idx in sorted_H]
    pos_in_sorted_H = [0] * N
    for idx in range(N):
        original_i = sorted_H[idx][2]
        pos_in_sorted_H[original_i] = idx
    
    # Segment Tree Node: (max_val, second_max)
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [ (0, -float('inf')) ] * (2 * self.size)
            for i in range(self.n):
                self.tree[self.size + i] = (data[i], -float('inf'))
            for i in range(self.size - 1, 0, -1):
                left = self.tree[2*i]
                right = self.tree[2*i +1]
                max_val = max(left[0], right[0])
                if left[0] > right[0]:
                    second_max = max(left[1], right[0])
                else:
                    second_max = max(right[1], left[0])
                self.tree[i] = (max_val, second_max)
        
        def query(self, l, r):
            if l > r:
                return (-float('inf'), -float('inf'))
            res_max = -float('inf')
            res_second = -float('inf')
            l += self.size
            r += self.size
            while l <= r:
                if l % 2 == 1:
                    current_max, current_second = self.tree[l]
                    new_max = max(res_max, current_max)
                    if res_max > current_max:
                        new_second = max(res_second, current_max)
                    else:
                        new_second = max(current_second, res_max)
                    res_max, res_second = new_max, new_second
                    l += 1
                if r % 2 == 0:
                    current_max, current_second = self.tree[r]
                    new_max = max(res_max, current_max)
                    if res_max > current_max:
                        new_second = max(res_second, current_max)
                    else:
                        new_second = max(current_second, res_max)
                    res_max, res_second = new_max, new_second
                    r -= 1
                l >>= 1
                r >>= 1
            return (res_max, res_second)
    
    # Prepare data for segment tree
    data_for_segment = [t for h, t, idx in sorted_H]
    st = SegmentTree(data_for_segment)
    
    max_T = [0] * N
    for i in range(N):
        Ti = T[i]
        Hi = H[i]
        # Find k: upper_bound of Ti in H_list
        k = bisect.bisect_right(H_list, Ti)
        if k == 0:
            current_max = -float('inf')
            current_second = -float('inf')
        else:
            current_max, current_second = st.query(0, k-1)
        # Check if city i is in the range [0, k-1]
        pos_i = pos_in_sorted_H[i]
        if pos_i < k:
            # City i is in the range
            if current_max == Ti:
                # Need to use second_max
                if current_second == -float('inf'):
                    # No other elements
                    computed_max = -float('inf')
                else:
                    computed_max = current_second
            else:
                computed_max = current_max
        else:
            computed_max = current_max
        max_T[i] = computed_max
    
    # Process queries
    output = []
    for A, B in queries:
        H_B = H[B]
        T_A = T[A]
        if H_B <= T_A:
            output.append('1')
        else:
            if max_T[A] >= H_B:
                output.append('2')
            else:
                output.append('-1')
    print('\n'.join(output))

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