ABC023 C.収集王

問題

R*Cのマスに飴がN個置かれている。同じマスには2つ以上飴は存在しない。
あるマスに立った時、そのマスと同じ行と列にあるすべての飴を手に入れることができる。
獲得する飴がちょうどK個になるようなマスはいくつあるか。

1<=R,C,K<=10^5
K<=N<=10^5

考え方

行方向、列方向それぞれでその行、列に存在する飴の個数を保持する配列cntR[i],cntC[j]を用意すると、数えるべきマスはcntR[i]+cntC[j]==KまたはK+1となっている部分しかないことがわかる。

cntR[i]+cntC[j]==Kの場合は、マスに飴がないとき該当し、K+1の場合は、マスに飴があるとき該当している。
したがって、合計がKとなるようなマスをすべて求めておいて、飴があるマスについて、合計がKならば覗いて、K+1なら増やす、という計算をすればよい。

cntR[i]+cntC[j]==Kとなるマスの個数は「飴の個数がa個のマスがb個」のような配列を用意しておけば、K+1回で求められる。

反省

考えながら書いてしまって意味不明なことやってた。
桁あふれはちゃんと考える。