結果

問題 No.1394 Changing Problems
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:45:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,437 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 140,408 KB
最終ジャッジ日時 2025-06-12 20:45:52
合計ジャッジ時間 7,583 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    A = list(map(int, data[idx:idx+N]))
    idx += N
    Q = int(data[idx])
    idx += 1
    queries = []
    for _ in range(Q):
        i = int(data[idx])-1
        x = int(data[idx+1])
        queries.append((i, x))
        idx +=2
    
    c = N-2
    d = N-1
    x = [a - c for a in A]
    x_sorted = sorted(x)
    prefix = [0]*(N+1)
    for i in range(N):
        prefix[i+1] = prefix[i] + x_sorted[i]
    
    def compute_sum(m):
        res = 0
        for xi in x_sorted:
            if xi > m:
                break
            temp = (m - xi) // d
            res += temp
        return res
    
    for i, val in queries:
        A[i] = val
        x[i] = A[i] - c
        x_sorted = sorted(x)
        prefix = [0]*(N+1)
        for i in range(N):
            prefix[i+1] = prefix[i] + x_sorted[i]
        
        S = sum(A)
        m_min = max(0, S - N*(N-2))
        low = m_min
        high = m_min
        while True:
            s = compute_sum(high)
            if s >= high:
                break
            high += 1
        while low <= high:
            mid = (low + high) // 2
            s = compute_sum(mid)
            if s >= mid:
                high = mid -1
            else:
                low = mid +1
        print(low)

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