[백준/BOJ] 백준 9571번 : Crowded Cows

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

9571번: Crowded Cows

 

입력받은 소들의 정보를 x 좌표 기준으로 정렬을 해서 해당 소들(vector<pair<int, int>> cow)의 인덱스(i)를 기준으로 세그먼트 트리를 만들고, 각 소마다 왼쪽과 오른쪽 d 범위를 세그먼트 트리 쿼리를 통해 해당 소의 크기보다 2배 이상 크기의 소가 범위 안에 속하는지 확인하여 붐비는 소인지 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n;
int d;
vector<pair<int, int>> cow;
int result = 0;

vector<int> max_sgmtt(50005 * 4);

int MakeSgmtt(int here, int left_range, int right_range) {

	if (left_range == right_range) {
		return max_sgmtt[here] = cow[left_range].second;
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (left_range + right_range) / 2;

	return max_sgmtt[here] = max(MakeSgmtt(left_child, left_range, mid), MakeSgmtt(right_child, mid + 1, right_range));
}

int QuerySgmtt(int here, int left_range, int right_range, int left_find, int right_find) {

	if (right_range < left_find || right_find < left_range) {
		return -1;
	}

	if (left_find <= left_range && right_range <= right_find) {
		return max_sgmtt[here];
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (left_range + right_range) / 2;

	return max(QuerySgmtt(left_child, left_range, mid, left_find, right_find), QuerySgmtt(right_child, mid + 1, right_range, left_find, right_find));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> d;

	for (int i = 0; i < n; i++) {
		int xi, hi;
		cin >> xi >> hi;

		cow.push_back(make_pair(xi, hi));
	}

	sort(cow.begin(), cow.end());
	cow.push_back(make_pair(2000000005, 2000000005));

	MakeSgmtt(0, 0, n - 1);

	int check_left_index = 0;
	int check_right_index = 0;
	for (int i = 0; i < n; i++) {

		//붐비는 소인지 확인할 소
		int here = cow[i].first;
		int here_height = cow[i].second;

		//현재 위치의 왼쪽 d범위 바깥에 있을때
		//check_left_index는 왼쪽 d범위의 안의 제일 왼쪽에 위치해야 한다
		while (cow[check_left_index].first < here - d) {
			check_left_index++;
		}

		//현재 위치 오른쪽 d범위 오른쪽 끝에 있지 않을때
		//check_right_index는 오른쪽 d범위의 안의 제일 오른쪽에 위치해야 한다
		//즉 범위 안에 속하면서 오른쪽으로 더 갈 수 있을때
		while (cow[check_right_index + 1].first <= here + d) {
			check_right_index++;
		}

		//붐비는 소 일때
		if ((QuerySgmtt(0, 0, n - 1, check_left_index, i) >= here_height * 2) && (QuerySgmtt(0, 0, n - 1, i, check_right_index) >= here_height * 2)) {
			result++;
		}
	}

	cout << result;

	return 0;
}