N×Mマス計算（K以上） [yukicoder 989]

https://yukicoder.me/problems/no/989

前提知識

• 二分探索

解説

https://yukicoder.me/submissions/430655

どこから手を付けようかという感じだが、何かを全探索して解きたいところ。
A[i]について全探索したときに、条件を満たすB[i]の個数が高速に計算できれば、
その個数の総和をとって答えとできる。
これは割と良い方針に見える。

A[i]×B[j]を考えたときに条件を満たすB[j]はある数以上になることが分かる。
つまり、単調性を持つ。
配列Bはソートしても問題ないので、二分探索をして、条件を満たす・満たさないの境界線を見つけよう。
この単調性は、opが和でも積でも同様なので、同じロジックが使える。

int N, M, K; char op;
ll B[101010], A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K >> op;
    rep(i, 0, M) cin >> B[i];
    rep(i, 0, N) cin >> A[i];

    sort(A, A + N);
    sort(B, B + M);

    ll ans = 0;
    rep(i, 0, N) {
        int ng = -1, ok = M;
        while (ng + 1 != ok) {
            int md = (ng + ok) / 2;

            ll res = A[i] + B[md];
            if (op == '*') res = A[i] * B[md];

            if (K <= res) ok = md;
            else ng = md;
        }
        ans += M - ok;
    }
    cout << ans << endl;
}