알고리즘/백준

2094 강수량 (라이브러리 사용 x)

아메숑 2019. 9. 1. 01:50

1. 문제

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

 

2094번: 강수량

문제 기상청에서는 매 해마다 그 해에 내린 비의 양을 측정하여 발표하는데, 이를 그 해의 강수량이라 한다. 이를 토대로 사람들은 어느 해에 몇 년 만에 비가 가장 많이 왔다는 식의 이야기를 하곤 한다. 하지만 사람은 자신의 경험과 감각에 의존하여 이야기하기 때문에, 이러한 이야기가 때론 거짓이 되기도 한다. 따라서 당신은, 기상청의 공식적인 측정 결과를 바탕으로 이러한 이야기들의 진실 여부를 가려내려 한다. 때로는 기상청의 공식적인 발표 자료를 구할 수

www.acmicpc.net

2. 코드

#include <iostream>
#include <algorithm>

using namespace std;

struct rain {
	int year, pre;
}R[50005];

int year[50005];
int precipitation[50005];

int tree[1 << 17];
struct segmentTree {
	int init(int index, int start, int end) {
		if (start == end) return tree[index] = R[start].pre;
		int mid = (start + end) / 2;
		return tree[index] = max(init(index * 2 + 1, start, mid), init(index * 2 + 2, mid + 1, end));
	}

	int get_max(int index, int start, int end, int left, int right) {
		if (start > right || end < left) return 0;
		else if (start >= left && end <= right) return tree[index];
		else {
			int mid = (start + end) / 2;
			return max(get_max(index * 2 + 1, start, mid, left, right), get_max(index * 2 + 2, mid + 1, end, left, right));
		}
	}
};

void quick_sort(int *p, int left, int right) {
	if (left >= right) return;
	int l = left - 1;
	int r = right + 1;
	int mid = p[(l + r) / 2];
	while (1) {
		while (p[++l] < mid);
		while (p[--r] > mid);
		if (l >= r) break;
		int tmp = p[l];
		p[l] = p[r];
		p[r] = tmp;
	}
	quick_sort(p, left, l - 1);
	quick_sort(p, r + 1, right);
}

//lower_bound
int get_idx(int *p, int val, int low, int high) {
	while (low < high) {
		int mid = (low + high) / 2;
		if (p[mid] < val) low = mid + 1;
		else high = mid;
	}
	return high;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> R[i].year >> R[i].pre;
		year[i] = R[i].year;
		precipitation[i] = R[i].pre;
	}

	quick_sort(precipitation, 0, n - 1);
	//좌표압축
	for (int i = 0; i < n; i++) {
		R[i].pre = get_idx(precipitation, R[i].pre, 0, n);
	}

	segmentTree seg;
	seg.init(0, 0, n - 1);

	cin >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;

		int fromIdx = get_idx(year, from, 0, n);
		int toIdx = get_idx(year, to, 0, n);

		if (fromIdx == toIdx || (from != R[fromIdx].year && to != R[toIdx].year)) {
			cout << "maybe\n";
			continue;
		}

		if (from != R[fromIdx].year) {
			int maxPre = seg.get_max(0, 0, n - 1, fromIdx, toIdx - 1);
			if (maxPre < R[toIdx].pre) cout << "maybe\n";
			else cout << "false\n";

		} else if (to != R[toIdx].year) {
			int maxPre = seg.get_max(0, 0, n - 1, fromIdx + 1, toIdx - 1);
			if (maxPre < R[fromIdx].pre || toIdx - 1 == fromIdx) cout << "maybe\n";
			else cout << "false\n";

		} else {
			int maxPre = seg.get_max(0, 0, n - 1, fromIdx + 1, toIdx - 1);

			if(R[toIdx].pre > R[fromIdx].pre) cout << "false\n";
			else {
				if(seg.get_max(0, 0, n - 1, fromIdx + 1, toIdx) > R[toIdx].pre) cout << "false\n";
				else {
					if (to - 1 == from) cout << "true\n";
					else if(toIdx - 1 == fromIdx) cout << "maybe\n";
					else if (maxPre == R[toIdx].pre) cout << "false\n";
					else if(fromIdx - toIdx == from - to) cout << "true\n";
					else cout << "maybe\n";
				}
				
			}
		}
	}
}

 

3. 후기

이 문제는 년도와 강수량의 값이 매우 크므로 좌표압축을하였다. year는 순서대로 들어오므로 강수량(pre)만 정렬해주었다.

그리고 두 년도 사이의 최대 강수량(압축된)을 반환하는 세그먼트 트리를 생성했다.

그리고 두 년도를 입력받아서 년도도 역시 압축시킨 뒤 세그먼트 트리를 이용해 구했다.