백준 7453 합이 0인 네 정수

백준 7453
4 개의 배열에서 합이 0인 순서쌍을 구하는 문제이다.
완전탐색으로 구하면 O(N^4)으로 시간초과이다.
그래서 배열 두 개를 미리 합해서 하나의 벡터에 다 넣어주고 정렬을 한다.
나머지 두 개의 배열을 이중포문으로 돌리면서 미리 전처리 해둔 벡터에 이분탐색을 함으로써 O(N^2logN) 시간복잡도를 지닌다.

#include <bits/stdc++.h>
using namespace std;
long long A[4001];
long long B[4001];
long long C[4001];
long long D[4001];
int n;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}

	sort(A, A + n);
	sort(B,B+ n);
	sort(C, C + n);
	sort(D, D + n);

	long long cnt = 0;

	vector<long long> v;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			v.push_back(A[i] + B[j]);
		}
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			long long sum = C[i] + D[j];

			cnt += upper_bound(v.begin(), v.end(), -sum) - lower_bound(v.begin(), v.end(), -sum);
		}
	}

	cout << cnt << '\n';
}