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; }