概要

各会員のポイント残高に対して、指定された加算処理を順番に適用し、結果が0未満にならないように調整しながら最終的なポイント残高を求める問題です。

考察

この問題は、単純に各処理を順番に適用していくだけで解くことができます。各処理では、対象となる会員の現在のポイント残高に指定された値を加算し、結果が0未満になる場合は0に調整します。制約条件が\(N, M \leq 10^5\)と大きいですが、各処理を1回ずつ適用するだけなので、十分に高速に処理できます。

素朴なアプローチとして、各処理ごとに該当する会員のポイント残高を更新していく方法が考えられます。ポイント調整の条件（0未満にならない）は、加算後の値をチェックするだけで実現できます。

アルゴリズム

1. 初期化: 各会員の初期ポイント残高を配列Sに読み込む
2. 処理の適用: 各ポイント調整処理について以下の操作を行う
   • 対象会員T_jの現在のポイント残高を取得
   • 現在の値にV_jを加算
   • 加算結果が0未満の場合は0に、そうでない場合は加算結果を新しいポイント残高として設定
3. 出力: すべての処理を適用した後の各会員のポイント残高を出力

計算量

• 時間計算量: \(O(M)\)
  • 各ポイント調整処理を1回ずつ処理するため
• 空間計算量: \(O(N)\)
  • 会員数\(N\)分の配列と、処理数\(M\)分の入力データを保持するため

実装のポイント

• 会員番号は1-indexedで与えられるため、配列アクセス時には-1して0-indexedに変換する必要があります

• 各処理ごとに現在のポイント残高を参照し、条件に応じて更新します

• 入力データの読み込みでは、一度にすべてのデータを読み込んでから処理する方法を採用しています

• 出力時には、リストの要素を文字列に変換してスペース区切りで出力します

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    S = list(map(int, data[2:2+n]))
    operations = []
    index = 2 + n
    for _ in range(m):
        t = int(data[index]) - 1
        v = int(data[index+1])
        index += 2
        operations.append((t, v))
    
    for t, v in operations:
        current = S[t]
        new_value = current + v
        if new_value < 0:
            S[t] = 0
        else:
            S[t] = new_value
    
    print(" ".join(map(str, S)))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。