백준 7453번 : 합이 0인 네 정수 (c++)

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.
A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력
합이 0이 되는 쌍의 개수를 출력한다.

예제 입력 1 
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
예제 출력 1 
5

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

ll a[4000];
ll b[4000];
ll c[4000];
ll d[4000];
ll arr[4000 * 4000];
ll brr[4000 * 4000];
int N,rr;

int searchNum(int index, int op) {
	int k = index + op;
	int cnt = 0;
	while (k >= 0 && k < (N * N) && brr[index] == brr[k]) {
		if (rr > k)rr = k;
		k += op;
		cnt++;
	}
	return cnt;
}


int binarySearch(ll num) {
	int L = 0;
	int R = rr;

	while (L <= R) {
		int mid = (L + R) / 2;
		if (num == brr[mid]) {
			rr = mid;
			return searchNum(mid, 1) + searchNum(mid, -1) + 1;
		}
		else if (num < brr[mid]) R = mid - 1;
		else L = mid + 1;
	}
	return 0;
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> N;
	int k = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			arr[k] = a[i] + b[j];
			brr[k] = c[i] + d[j];
			k++;
		}
	}

	sort(arr, arr + k);
	sort(brr, brr + k);

	long long ans = 0, temp = 0;
	rr = k;

	for (int i = 0; i < k; i++)
	{
		if (i > 0 && arr[i - 1] == arr[i]) {
			ans += temp;
		}
		else {
			temp = binarySearch(-arr[i]);
			ans += temp;
		}
	}

	cout << ans;

	return 0;
}