[ BOJ ] 3770 : 대한민국 ( PLATINUM 5 ) / C

문제

대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다.

대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다)

고속도로가 서로 교차하는 곳에는 휴게소를 지으려고 한다. 한 점에서 교차하는 고속도로는 최대 2개이다. 고속도로가 주어졌을 때, 고속도로가 교차하는 곳의 개수를 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고속도로의 정보는 숫자 2개로 이루어져 있다. 첫 번째 숫자는 동해안에 있는 도시의 번호이고, 두 번째 숫자는 서해안에 있는 도시의 번호이다.

고속도로의 개수는 40만개보다 작거나 같으며, 문제의 정답이 263-1보다 작거나 같은 경우만 입력으로 주어진다.

출력

각 테스트 케이스에 대해서, 교차점의 수를 케이스 번호와 함께 출력한다.

풀이 과정

교차개수를 세는 Segment tree 문제이다. 다수의 테스트 케이스가 있기 때문에 초기화만 더해주면 된다.

#include <stdio.h>
#define QSIZE 400005
#define NSIZE 1005
typedef long long LL;

int query[QSIZE][2];
int query_size = 0;

int sort_query[QSIZE][2];

LL tree[NSIZE * 4] = { 0, };

void query_merge(int start, int mid, int end) {
	int leftidx = start;
	int rightidx = mid + 1;
	int allidx = start;

	while (leftidx <= mid && rightidx <= end) {
		if (query[leftidx][0] < query[rightidx][0]) {
			sort_query[allidx][0] = query[leftidx][0];
			sort_query[allidx][1] = query[leftidx][1];
			allidx += 1;
			leftidx += 1;
		}
		else if (query[leftidx][0] > query[rightidx][0]) {
			sort_query[allidx][0] = query[rightidx][0];
			sort_query[allidx][1] = query[rightidx][1];
			allidx += 1;
			rightidx += 1;
		}
		else {
			if (query[leftidx][1] < query[rightidx][1]) {
				sort_query[allidx][0] = query[leftidx][0];
				sort_query[allidx][1] = query[leftidx][1];
				allidx += 1;
				leftidx += 1;
			}
			else {
				sort_query[allidx][0] = query[rightidx][0];
				sort_query[allidx][1] = query[rightidx][1];
				allidx += 1;
				rightidx += 1;
			}
		}
	}

	while (leftidx <= mid) {
		sort_query[allidx][0] = query[leftidx][0];
		sort_query[allidx][1] = query[leftidx][1];
		allidx += 1;
		leftidx += 1;
	}
	while (rightidx <= end) {
		sort_query[allidx][0] = query[rightidx][0];
		sort_query[allidx][1] = query[rightidx][1];
		allidx += 1;
		rightidx += 1;
	}

	for (int i = start; i <= end; i++) {
		query[i][0] = sort_query[i][0];
		query[i][1] = sort_query[i][1];
	}
}

void query_merge_sort(int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;
		query_merge_sort(start, mid);
		query_merge_sort(mid + 1, end);
		query_merge(start, mid, end);
	}
}

void update(int start, int end, int idx, int what, int value) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] += value;
		return;
	}

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what, value);
	update(mid + 1, end, idx * 2 + 1, what, value);

	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

LL interval_sum(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	return interval_sum(start, mid, idx * 2, left, right) + interval_sum(mid + 1, end, idx * 2 + 1, left, right);
}

int main(void) {
	int test_case;
	scanf("%d", &test_case); 

	for (int t = 0; t < test_case; t++) {
		int n, m, k;
		scanf("%d %d %d", &n, &m, &k);
		query_size = 0;

		for (int i = 0; i < k; i++) {
			int a, b;
			scanf("%d %d", &a, &b);

			query[query_size][0] = a - 1;
			query[query_size++][1] = b - 1;
		}

		query_merge_sort(0, query_size - 1);


		LL result = 0;
		for (int i = 0; i < query_size; i++) {
			result += interval_sum(0, m - 1, 1, query[i][1], m - 1);
			update(0, m - 1, 1, query[i][1] - 1, 1);
		}

		for (int i = 0; i < query_size; i++) update(0, m - 1, 1, query[i][1] - 1, -1);

		printf("Test case %d: %lld\n", t + 1, result);
	}
	return 0;
}