백준 2094 강수량(STL없음)

문제

www.acmicpc.net/problem/2094

2094번: 강수량

 

코드

#include <iostream>
using namespace std;

#define MAXN 50001
#define max(a,b) (a<b?b:a)
#define TRUE 1
#define FALSE 0
#define MAYBE -1


int year[MAXN], tree[MAXN << 2]; //tree[year_index+base]=rain
int n, m, base, x, y;

int getIndex(int  val)
{
	register int le = 0, ri = n, mid;
	while (le < ri)
	{
		mid = (le + ri) >> 1;
		if (year[mid] < val)
			le = mid + 1;
		else
			ri = mid;
	}
	return ri;
}


int getMax(int le, int ri)
{
	int ret = 0;
	le += base; ri += base;

	while (le <= ri) {
		if (le & 1)ret = max(ret, tree[le]), le++;
		if (!(ri & 1))ret = max(ret, tree[ri]), ri--;
		le /= 2;
		ri /= 2;
	}
	return ret;
}

int judge()
{
	register int xIndex, yIndex, xChk, yChk;
	xIndex = getIndex(x);
	yIndex = getIndex(y);
	xChk = xIndex < n && year[xIndex] == x ? 1 : 0;
	yChk = yIndex < n && year[yIndex] == y ? 1 : 0;

	if (xChk && yChk && tree[base + yIndex] < tree[base + xIndex]) return FALSE;

	int maxVal, findxIdx = xIndex, findyIdx = yIndex;
	while (x <= year[findxIdx])
			findxIdx--;
	while (y >= year[findyIdx])
		findyIdx++;

	maxVal = getMax(findyIdx, findxIdx);

	if (xChk && tree[base + xIndex] <= maxVal) return FALSE;
	if (yChk && tree[base + yIndex] <= maxVal) return FALSE;

	if (xChk&& yChk && y - x == yIndex - xIndex) return TRUE;
	return MAYBE;
}

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

	cin >> n;
	base = 1;
	while (base < n) base <<= 1;
	register int i, idx;
	year[n] = 1e9;

	for (i = 0; i < n; i++)
	{
		cin >> year[i] >> tree[base + i];

		idx = (base + i) / 2;
		while (idx)
		{
			tree[idx] = max(tree[(idx << 1)], tree[((idx << 1) | 1)]);
			idx >>= 1;
		}
	}


	cin >> m;
	while (m--)
	{
		cin >> y >> x;
		int ans = judge();
		if (ans == TRUE)
			cout << "true" << '\n';
		else if (ans == MAYBE)
			cout << "maybe" << '\n';
		else
			cout << "false" << '\n';
	}

	return 0;
}

잼있는 문제