結果

問題 No.2223 Merged Med
ユーザー gew1fw
提出日時 2025-06-12 20:58:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,349 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 86,656 KB
最終ジャッジ日時 2025-06-12 21:02:42
合計ジャッジ時間 8,362 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 1 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N, Q = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.min1 = [0] * (2 * self.size)
            self.min2 = [0] * (2 * self.size)
            for i in range(self.size):
                if i < self.n:
                    self.min1[self.size + i] = data[i]
                    self.min2[self.size + i] = float('inf')
                else:
                    self.min1[self.size + i] = float('inf')
                    self.min2[self.size + i] = float('inf')
            for i in range(self.size - 1, 0, -1):
                self.push_up(i)
        
        def push_up(self, i):
            left = 2 * i
            right = 2 * i + 1
            temp = []
            temp.append(self.min1[left])
            temp.append(self.min2[left])
            temp.append(self.min1[right])
            temp.append(self.min2[right])
            temp = sorted(temp)
            self.min1[i] = temp[0]
            self.min2[i] = temp[1]
        
        def query_range(self, l, r):
            res1 = float('inf')
            res2 = float('inf')
            l += self.size
            r += self.size
            while l <= r:
                if l % 2 == 1:
                    self.update_res(res1, res2, self.min1[l], self.min2[l])
                    l += 1
                if r % 2 == 0:
                    self.update_res(res1, res2, self.min1[r], self.min2[r])
                    r -= 1
                l >>= 1
                r >>= 1
            return (res1, res2)
        
        def update_res(self, res1, res2, new1, new2):
            candidates = [res1, res2, new1, new2]
            candidates = sorted(candidates)
            new_res1 = candidates[0]
            new_res2 = candidates[1]
            return (new_res1, new_res2)
    
    st = SegmentTree(A)
    
    for _ in range(Q):
        l, r = map(int, sys.stdin.readline().split())
        if l == r:
            print(A[l-1])
            continue
        a, b = st.query_range(l-1, r-1)
        print(b if b != float('inf') else a)
    
if __name__ == '__main__':
    main()
0