結果

問題 No.2223 Merged Med
ユーザー lam6er
提出日時 2025-03-31 17:51:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,063 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 76,416 KB
最終ジャッジ日時 2025-03-31 17:52:20
合計ジャッジ時間 10,639 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    queries = []
    for _ in range(Q):
        l = int(input[ptr])-1
        ptr +=1
        r = int(input[ptr])-1
        ptr +=1
        queries.append((l, r))

    # Process queries
    for l, r in queries:
        sub = A[l:r+1]
        sub_sorted = sorted(sub)
        n = len(sub)
        ans = None
        # We check each possible x in sorted order to find the minimal possible
        for x in sub_sorted:
            # Now, check if x can be the median of some X'
            # after replacing some segment.
            # X' is formed by replacing [a..b] with med of sub[a..b]
            found = False
            # Check: replace a segment such that the new array's med is x.
            # X' has elements not in [a..b] plus med(a..b)
            # Try all possible a and b, but this is O(n^2)
            for a in range(n):
                for b in range(a, n):
                    # Get med of sub[a..b]
                    seg = sub[a:b+1]
                    seg_sorted = sorted(seg)
                    m = len(seg)
                    med_idx = (m//2)
                    y = seg_sorted[med_idx]
                    # New array is sub[0..a-1] + [y] + sub[b+1..n-1]
                    # To compute the new array's med, we need all elements:
                    new_array = sub[:a] + [y] + sub[b+1:]
                    new_sorted = sorted(new_array)
                    new_len = len(new_array)
                    med_new_idx = (new_len // 2)
                    med_new = new_sorted[med_new_idx]
                    if med_new == x:
                        found = True
                        break
                if found:
                    break
            if found:
                ans = x
                break
        print(ans)

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