結果

問題 No.1394 Changing Problems
ユーザー lam6er
提出日時 2025-04-09 20:56:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,810 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 142,732 KB
最終ジャッジ日時 2025-04-09 20:57:49
合計ジャッジ時間 5,922 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    Q = int(input[ptr])
    ptr +=1
    queries = []
    for _ in range(Q):
        i = int(input[ptr])-1
        x = int(input[ptr+1])
        queries.append( (i, x) )
        ptr +=2

    # Precompute initial C and check_all
    N_minus_2 = N -2
    d = N-1
    current_A = A.copy()
    sum_A = sum(current_A)
    max_A = max(current_A)
    C = [ N_minus_2 - a for a in current_A ]

    # Helper function to check if all elements are <= N-2
    def check_all():
        return all( a <= N_minus_2 for a in current_A )

    # Precompute initial state
    all_le = check_all()

    for iq, xq in queries:
        old_val = current_A[iq]
        current_A[iq] = xq
        sum_A = sum_A - old_val + xq
        # Update max_A
        if xq > max_A:
            # Could be new max, need to check
            max_A = max(current_A)
        else:
            # If old_val was the previous max, we need to recompute
            if old_val == max_A:
                max_A = max(current_A)
        # Check if all elements are <= N_minus_2
        all_le = check_all()
        if all_le:
            print(0)
            continue

        # Compute m_low
        S = sum_A
        m_low1 = S - N * N_minus_2
        m_low2 = max( max( a - N_minus_2 for a in current_A ), 0 )
        m_low = max( m_low1, m_low2 )
        m_low = max( m_low, 0 )

        # Now check for each m from m_low onwards until sum_floor >=m
        found = False
        current_C = [ N_minus_2 - a for a in current_A ]

        for m_candidate in [m_low, m_low +1, m_low +2, m_low +3]:
            if m_candidate <0:
                continue
            sum_floor = 0
            for c in current_C:
                numerator = m_candidate + c
                if numerator <0:
                    term =0
                else:
                    term = numerator // d
                sum_floor += term
            if sum_floor >= m_candidate:
                print(m_candidate)
                found = True
                break
        if found:
            continue

        # If not found in small increments, which should not happen under contest conditions
        # Fallback (not expected to be called)
        m_candidate = m_low
        while True:
            sum_floor =0
            for c in current_C:
                numerator = m_candidate + c
                if numerator <0:
                    term =0
                else:
                    term = numerator //d
                sum_floor += term
            if sum_floor >= m_candidate:
                print(m_candidate)
                break
            m_candidate +=1

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