/* Sample solution to "Worst Weather Ever" problem from NCPC 2005. * * Complexity: O(n + m log n) per test case. * * Author: Per Austrin */ #include #include using namespace std; typedef pair pii; int A, B, C, D, E, F, G, H; bool solve(int P) { pii known[55000]; int prev[55000], next[55000]; int n, m; if (scanf("%d", &n) != 1 || !n) return false; ++n; for (int i = 1; i < n; ++i) scanf("%d%d", &known[i].first, &known[i].second); known[0] = pii(-(1<<30), 1<<30); known[n] = pii(1<<30, 1<<30); for (int i = 1, j = 0, k = n; i <= n; j = i, k = n-i, ++i) { while (known[j].second < known[i].second) j = prev[j]; prev[i] = j; while (known[k].second < known[n-i].second) k = next[k]; next[n-i] = k; } ++n; scanf("%d", &m); if (P) printf("\n"); for (int i = 0; i < m; ++i) { int x, y; scanf("%d%d", &y, &x); pii *X = upper_bound(known, known+n, pii(x, -1)); pii *Y = upper_bound(known, known+n, pii(y, -1)); if (X->first == x && Y->first == y) { pii *Z = known + prev[X - known]; if (Y != Z) printf("false\n"), ++A; else if (X - Y == x - y) printf("true\n"), ++B; else printf("maybe\n"), ++C; } else if (X->first == x) { pii *Z = known + prev[X - known]; if (Z->first < y) printf("maybe\n"), ++D; else printf("false\n"), ++E; } else if (Y->first == y) { pii *Z = known + next[Y - known]; if (Z->first > x) printf("maybe\n"), ++F; else printf("false\n"), ++G; } else { printf("maybe\n"), ++H; } } return true; } int main() { A = B= C= D= E= F= G= H= 0; for (int i = 0; solve(i); ++i); fprintf(stderr, "case distr: %d %d %d %d %d %d %d %d\n", A, B, C, D, E, F, G, H); return 0; }