https://emtubasa.hateblo.jp/entry/2019/02/14/000000

解法

まずは $i$ 行目を選択すると固定して考えてみることにします。
$i$ 行目を選択した場合にアメが $r_{i}$ 個得られるとします。
同様に、 $j$ 列目を選択した場合に $c_{j}$ 個得られるとします。
この時、 $K$ 個のアメを得るには、 $r_{i} + c_{j} = K$ を満たすものならばいいように見えるかもしれませんが、実は違います。
$(i,j)$ にアメが存在していた場合、 $r_{i}$ および $c_{j}$ それぞれにそのアメがカウントされているため、実際は $K-1$ 個である可能性があるからです。
同様に、 $(i,j)$ にアメが存在していた場合で、実際に $(i,j)$ を選択して $K$ 個得られるパターンというのは、 $r_{i} + c_{j}$ を計算すると $K+1$ となります。
しかし、 $(i,j)$ にアメが存在していない場合は、 $r_{i} + c_{j} = K$ となるマスが、求めるマスになります。
$(i,j)$ の種類は $RC$ なので、全てを探索するわけにはいきませんが、 $r_{i} + c_{j} = K$ となるようなマスの個数を求めるのは、二分探索を活用することで求めることができます。よって、うまいこと工夫をして、最初に述べた2種類のコーナーケースを考慮しつつ、計算ができるようにしたいです。
そこで、以下のようにすればよいことになります。

$r_{i} + c_{j} = K$ となるようなマスの個数を求める
$i$ を固定したとき、 $c_{j} = K - r_{i}$ となるような $j$ の個数がわかればよいです。これは、 $c_{j}$ を昇順にソートすることで、二分探索を利用すれば $K - r_{i}$ のとなっている $c_{j}$ の個数を求めることができます(upper_boundとlower_boundを求め、前者から後者をひけばよいです)。これを全ての $i$ について行えば $O(R log C)$ で計算できます。
$N$ 個のアメの座標 $(x,y)$ について、 $r_{x} + c_{y} = K$ となっているものが存在するかどうかを調べる
存在していたら、上の計算から引いてあげる必要があります。
$N$ 個のアメの座標 $(x,y)$ について、 $r_{x} + c_{y} = K+1$ となっているものが存在するかどうかを調べる
存在していたら、上の計算に足してあげる必要があります。

以上の計算をすることで、重複なく、求めたいマスの個数を数え上げることができます。

感想

最初、 $R$ について二分探索をしたときに、辻褄が合わないマスが出てくることはすぐにわかったのですが、そこをどうするかで悩みました。
このような都合の悪いケースが出てきたときに、他の解法を探すか、そのケースだけうまく辻褄を合わせる方法があるかを調べる2択が発生すると思うのですが、今回ははずれを引きました。
ここら辺の勘というか経験といいますか、どちらについて考えればいいかがわかれば、ぐっと考察時間が短くなるような気はするのですが…