技術室奥プログラミングコンテスト#4 Day1：I - school competition 1

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i

解法

A と B を昇順にソートしておき，各 A_i よりも真に大きい B_i の個数を調べる．これは std::upper_bound() を用いて各 A_i につき O(logM) で計算することができる．この個数を前から累積和として持っておく．その後，各 A_i よりも真に小さい B_i の個数を調べる．これも前と同様にして std::lower_bound() を用いて計算できる．この個数と前で求めた A_(i + 1) ~ A_N よりも真に大きい B_i の個数の累積和を掛け合わせたものが P = A_i と固定したときの通り数．これらを足し合わせたものが答えになる．O(NlogM)．