n개의 배열 a, b, c가 주어진다.
a[i] < b[j] < c[k] 를 만족시키는 모든 쌍의 개수를 구하는 문제.

Solution

순서 상관 없으니 정렬부터 해보면 뭔가 보인다.
b를 기준으로 살펴보자. b의 원소 중 하나를 정했다면

b보다 작은 a 배열 원소의 개수 X b보다 큰 c 배열 원소의 개수

가 해당 b 원소를 뽑았을 때 만들 수 있는 경우의 수가 된다.

모든 n에 대해 돌리면서 b의 원소를 기준으로 a, c 배열에 대해 이분 탐색을 사용하면 된다.

Code

#include <iostream>
#include <algorithm>
using namespace std;

int a[100000];
int b[100000];
int c[100000];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}

	for (int i = 0; i < n; i++)
	{
		cin >> c[i];
	}

	sort(a, a + n);
	sort(b, b + n);
	sort(c, c + n);

	long long ans = 0;

	for (int i = 0; i < n; i++)
	{
		int aIdx = lower_bound(a, a + n, b[i]) - a - 1;
		int cIdx = upper_bound(c, c + n, b[i]) - c;

		if (aIdx < 0 || cIdx >= n)
		{
			continue;
		}

		ans += (long long)(aIdx + 1) * (n - cIdx);
	}

	cout << ans << endl;
}

ARC_084_A / ABC_077_C - Snuke Festival

Problem link

Problem Summary

Solution

Code