/* * Sample solution for "Worst Weather Ever". * * Runnig time: O(n + m log n) * * Author: Nils Grimsmo */ #include #include #include #include #include #include #ifdef _WIN32 #include #else #include #endif using namespace std; #ifndef _WIN32 using namespace __gnu_cxx; #endif #define MIN(A,B) ((A)<(B)?(A):(B)) #define MAX(A,B) ((A)>(B)?(A):(B)) typedef map::iterator mit; class MaxTable { public: int levels; int** table; int n; MaxTable(int _n, int* vals) { n = _n; levels = (int)ceil(log((double)n) / log(2.0)) + 1; table = new int*[levels]; table[0] = vals; for (int i = 1; i < levels; i++) { int mf = n >> i; int mc = mf + ((n & ((1 << i) - 1)) > 0); table[i] = new int[mc]; for (int j = 0; j < mf; j++) { table[i][j] = MAX(table[i-1][j * 2], table[i-1][j * 2 + 1]); } if (mf < mc) { table[i][mf] = table[i-1][mf * 2]; } } } ~MaxTable() { for (int i = 1; i < levels; i++) { delete[] table[i]; } delete table; } // inclusive borders int max(int start, int end) { if (end < start) { return INT_MIN; } int s = start; int e = end; int lvl = 0; int max = table[0][s]; while (s <= e) { max = MAX(max, MAX(table[lvl][s], table[lvl][e])); if ((s & 1) == 0) { s >>= 1; } else { s >>= 1; s += 1; } if ((e & 1) == 1) { e >>= 1; } else { e >>= 1; e -= 1; } lvl += 1; } return max; } static void sanitycheck() { int n = 100; int cases = 100; for (int c = 0; c < cases; c++) { int* data = new int[n]; for (int j = 0; j < n; j++) { data[j] = rand() % (n * 2) - n; } MaxTable mt(n, data); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int max = INT_MIN; for (int k = i; k <= j; k++) { max = MAX(max, data[k]); } assert(max == mt.max(i, j)); } } } fprintf(stderr, "sane\n"); } }; int main() { const int MAX_N = 50000; //MaxTable::sanitycheck(); int* year = new int[MAX_N+1]; // room for dummy INT_MAX year int* rain = new int[MAX_N]; int* nextunk = new int[MAX_N]; // next unknown year index, points forward for (int cas = 0; ; cas++) { int n, m; scanf("%d", &n); if (n == 0) { return 0; } else if (cas) { printf("\n"); } for (int i = 0; i < n; i++) { scanf("%d %d", &year[i], &rain[i]); } year[n] = INT_MAX; int unset = 0; for (int i = 1; i < n; i++) { if (year[i] - year[i-1] > 1) { while (unset < i) { nextunk[unset] = year[i-1] + 1; unset++; } } } while (unset < n) { nextunk[unset++] = year[n-1] + 1; } MaxTable mt(n, rain); scanf("%d", &m); for (int j = 0; j < m; j++) { int X, Y; scanf("%d %d", &Y, &X); int* yi = lower_bound(year, year + n + 1, Y); int* xi = lower_bound(year, year + n + 1, X); bool yf = Y == *yi; bool xf = X == *xi; int yp = yi - year; int xp = xi - year; if (yf && xf && rain[xp] > rain[yp]) { printf("false\n"); } else if (xf && mt.max(yp + yf, xp - 1) >= rain[xp]) { printf("false\n"); } else if (yf && !xf && mt.max(yp + 1, xp - 1) > rain[yp]) { printf("false\n"); } else if (xf && rain[xp] == 0 && Y + 1 == X) { printf("true\n"); } else if (!yf || !xf) { printf("maybe\n"); } else if (nextunk[yp] < X) { printf("maybe\n"); } else { printf("true\n"); } } } }