[백준/BOJ] 백준 9571번 : Crowded Cows
2023. 3. 15. 00:47ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/9571
입력받은 소들의 정보를 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;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 2026번 : 소풍 (0) | 2023.03.15 |
---|---|
[백준/BOJ] 백준 12012번 : Closing the Farm (Gold) (0) | 2023.03.15 |
[백준/BOJ] 백준 2543번 : 초고속철도 (0) | 2023.03.15 |
[백준/BOJ] 백준 17267번 : 상남자 (0) | 2023.03.14 |
[백준/BOJ] 백준 16468번 : 크리스마스 트리 꾸미기 (0) | 2023.03.14 |