こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【2日目】」ということで、2023年12月2日に行われたABC331のC問題を解きたいと思います。

問題

C - Sum of Numbers Greater Than Me

長さ $N$ の数列 $A=(A_1,…,A_N)$ が与えられます。

$i=1,…,N$ のそれぞれについて次の問題を解いてください。

問題： $A$ の要素のうち $A_i$ より大きな要素全ての和を求めよ。

入力は全て整数である

入力は以下の形式で標準入力から与えられる。

$N$

$A_1 ... A_N$

各 $1 \leqq k \leqq N$ について、 $i=k$ に対する問題の答えを $B_k$ とする。 $B_1,…,B_N$ をこの順に空白区切りで出力せよ。

要素数1000000個の配列countを用意します。 $A_i$ 番目に $A_i$ を加算していきます。その後countを後ろから前に向かって累積和を行い、countの $A_i+1$ 番目を出力してACしました。

~~以上の和だったので累積和を実行したらうまくいきました。 $A_i$ の制約が大きすぎるとメモリ制限超過するので注意です。