评测

#include<cstdio>
#include<unordered_map>
#include<cmath>
#include<cstring>

const int N = 50005;
int n, m, cnt, a[N << 1], st[2][21][N << 1];
std::unordered_map<int, int> mp;

inline int max(const int &a, const int &b) {return a > b ? a : b;}
inline int min(const int &a, const int &b) {return a < b ? a : b;}

int main() {
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	memset(st[1], 0x3f, sizeof st[1]);
	scanf("%d", &n);
	int last = -2147483647, y, r;
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &y, &r);
		if(last != -2147483647 && y != last + 1) {
			++cnt;
			st[1][0][cnt] = 0;
		}
		last = y;
		a[++cnt] = r;
		mp[y] = cnt;
		st[0][0][cnt] = st[1][0][cnt] = a[cnt];
	}
	for(int j = 1; j <= 20; ++j) {
		for(int i = 1; i + (1 << j) - 1 <= cnt; ++i) {
			st[0][j][i] = max(st[0][j - 1][i], st[0][j - 1][i + (1 << (j - 1))]);
			st[1][j][i] = min(st[1][j - 1][i], st[1][j - 1][i + (1 << (j - 1))]);
		}
	}
	scanf("%d", &m);
	while(m--) {
		int x, y;
		scanf("%d%d", &y, &x);
		int tx = mp[x], ty = mp[y] + 1;
		if(tx == 0 && ty == 1) {
			printf("maybe\n");
		} else if(tx == 0) {
			--ty;
			while(tx == 0 && x > y) {
				tx = mp[--x];
			}
			if(x > y) {
				int k = std::log2(tx - ty + 1);
				if(max(st[0][k][ty], st[0][k][tx - (1 << k) + 1]) != a[ty]) {
					printf("false\n");
				} else {
					if(tx > ty + 1) {
						k = std::log2(tx - ty + 2);
						if(max(st[0][k][ty + 1], st[0][k][tx - (1 << k) + 1]) == a[ty] - 1) {
							printf("false\n");
							continue;
						}
					}
					printf("maybe\n");
				}
			} else {
				printf("maybe\n");
			}
		} else if(ty == 1) {
			while(ty == 1 && y < x) { 
				ty = mp[++y] + 1;
			}
			if(y < x) {
				--ty;
				int k = std::log2(tx - ty + 1);
				if(max(st[0][k][ty], st[0][k][tx - (1 << k) + 1]) != a[tx]) {
					printf("false\n");
				} else {
					if(tx > ty + 1) {
						int k1 = std::log2(tx - ty);
						if(max(st[0][k1][ty], st[0][k1][tx - (1 << k1)]) == a[tx]) {
							printf("false\n");
							continue;
					}
				}
					printf("maybe\n");
				}
			} else {
				printf("maybe\n");
			}
		} else {
			int k = std::log2(tx - ty + 1);
			if(max(st[0][k][ty], st[0][k][tx - (1 << k) + 1]) != a[tx] || a[tx] > a[ty - 1]) {
				printf("false\n");
			} else {
				if(tx > ty + 1) {
					int k1 = std::log2(tx - ty);
					if(max(st[0][k1][ty], st[0][k1][tx - (1 << k1)]) == a[tx]) {
						printf("false\n");
						continue;
					}
				}
				if(min(st[1][k][ty], st[1][k][tx - (1 << k) + 1]) == 0) {
					printf("maybe\n");
				} else {
					printf("true\n");
				}
			}
		}
	}
	return 0;
}