Snuke Festival [AtCoder Regular Contest 084 C]

https://beta.atcoder.jp/contests/arc084/tasks/arc084_a

解説

https://beta.atcoder.jp/contests/arc084/submissions/1738206

使う中部のパーツを全探索する。
b番目の中部のパーツを使うとする。
すると、上部のパーツとして使えるのは大きさが[0,B[b])のもので、下部のパーツとして使えるのは大きさが(B[b],10^9]のものである。
これを高速にカウントするために、配列Aと配列Cをソートする。
上部のパーツとして使えるものの個数a = lower_bound(A, A+N, B[b])-A
下部のパーツとして使えるものの個数c = N - (upper_bound(C, C + N, B[b]) - C)
上部と下部の組合せは全部でac通りあり、この総和を取れば答え。

typedef long long ll;
int N, A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) cin >> C[i];
    sort(A, A + N);
    sort(C, C + N);
 
    ll ans = 0;
    rep(b, 0, N) {
        ll a = lower_bound(A, A + N, B[b]) - A;
        ll c = N - (upper_bound(C, C + N, B[b]) - C);
        ans += a * c;
    }
    cout << ans << endl;
}