2112.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2112 on 2006-01-20 at 17:58:39 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 51200;
const int INF = 1 << 30;
typedef pair<int, int> pii;

int main()
{
	pii year[MAX];
	int i, j, k, t = 0;
	int prev[MAX], next[MAX], n, m;

	year[0] = pii(-INF, INF);
	while(scanf("%d", &n) != EOF) {
		for(i = 1; i <= n; i++) 
			scanf("%d %d", &year[i].first, &year[i].second);
		year[++n] = pii(INF, INF);
		for(i = 1, j = 0, k = n; i <= n; j = i, k = n-i, i++) {
			while(year[j].second < year[i].second) j = prev[j];
			prev[i] = j;
			while(year[k].second < year[n-i].second) k = next[k];
			next[n-i] = k;
		}
		scanf("%d", &m);
		if(n == 1 && m == 0) break;
		else {
			if(t != 0) putchar('\n'); t++;
			for(i = 0; i < m; i++) {
				int b, e;
				scanf("%d %d", &b, &e);
				int Y = upper_bound(year, year+n, pii(b, 0)) - year;
				int X = upper_bound(year, year+n, pii(e, 0)) - year;
				if(year[Y].first == b && year[X].first == e) {
					if(prev[X] != Y) printf("false\n");
					else if(X-Y == e-b) printf("true\n");
					else printf("maybe\n");
				} else if(year[Y].first == b) {
					if(year[next[Y]].first > e) printf("maybe\n");
					else printf("false\n");
				} else if(year[X].first == e) {
					if(year[prev[X]].first < b) printf("maybe\n");
					else printf("false\n");
				} else printf("maybe\n");
			}
		}
	}

	return 0;
}