#include #include using namespace std; class Node { private: int ylo, yhi; // interval of years int mx; // max known rainfall in interval int ny; // number of known years in interval bool leaf; // true if this is a leaf Node *left, *right; void set(int y1, int y2, int m, int n, bool lf, Node *lft, Node *rte) { ylo=y1; yhi=y2; mx=m; leaf=lf; ny=n; left=lft; right=rte; }; public: void print(int n) { for (int i = 0; i < n; ++i) putchar(' '); putchar('('); printf("%d %d %d %d\n", ylo, yhi, mx, ny); if (!leaf) { left->print(n+2); right->print(n+2); } for (int i = 0; i < n; ++i) putchar(' '); printf(")\n"); } Node(int y, int fall) : ylo(y), yhi(y), mx(fall), ny(1), leaf(true), left(0), right(0) { }; Node(Node *u, Node *v) : ylo(u->ylo), yhi(v->yhi), mx(max(u->mx, v->mx)), ny(u->ny + v->ny), leaf(false), left(u), right(v) { }; /* Node(int y, int fall) { set(y, y, fall, 1, true, 0, 0); }; Node(Node *u, Node *v) { set(u->ylo, v->yhi, max(u->mx, v->mx), u->ny + v->ny, false, u, v); }; */ ~Node() { if (!leaf) { delete left; delete right; } }; /* return max known rain in interval years [y1,y2] * return -1 if no rainfall is known in interval * return 0 if y1 > y2 * (1) and (2) cover leaf case. */ int fall(int y1, int y2) { if (y1 > y2) return 0; if (y1 > yhi || y2 = yhi) return mx; // (2) return max(left->fall(y1, y2), right->fall(y1, y2)); }; int fall(int y) { return fall(y,y); }; /* return number of known years in interval [y1,y2] * (1) and (2) cover leaf case. */ int num(int y1, int y2) { if (y1 > yhi || y2 = yhi) return ny; // (2) return left->num(y1, y2) + right->num(y1, y2); // return max(left->num(y1, y2), right->num(y1, y2)); }; friend bool cmp(const Node*, const Node*); }; /* struct Cmp { bool operator()(const Node* u, const Node* v) const { return u->ylo < v->ylo; }; } */ bool cmp(const Node* u, const Node* v) { return u->ylo < v->ylo; } bool solve(int nc) { //fprintf(stderr, "Case %d:\n", nc+1); int n; Node **nodes; scanf("%d",&n); if(n==0) return false; nodes = new Node*[n]; int i,j; if (nc) printf("\n"); for(i=0; i < n; ++i) { int y,r; scanf("%d %d",&y, &r); nodes[i] = new Node(y,r); } sort(nodes, nodes+n, cmp); // for (i=0; i < n; ++i) nodes[i]->print(0); while (n>1) { i=j=0; while (jprint(0); } Node *stat = nodes[0]; // fprintf(stderr, " Tree done\n"); // stat->print(0); int m,y1,y2; scanf("%d", &m); for (i=0; i < m; ++i) { const char *s; s = "CANNOT HAPPEN"; scanf("%d %d", &y1, &y2); // is y1 the last time it rained >= y2? if (y1 >= y2) s = "y1 >= y2 MAKES NO SENSE"; else { // y1 < y2 int f1 = stat->fall(y1); int f2 = stat->fall(y2); int max_between = stat->fall(y1+1, y2-1); int num_between = stat->num(y1+1, y2-1); // fprintf(stderr, "%d %d %d %d\n", f1, f2, max_between, num_between); if (f1 < 0 && f2 < 0) s = "maybe"; else { // >= one of y1, y2 is known if (y1 == y2-1) { // no years between if (f2 == 0) s = "true"; else if (f1 < 0 || f2 < 0) s = "maybe"; else s = (f1 >= f2) ? "true" : "false"; } else if (f2 < 0) s = (max_between < f1) ? "maybe" : "false"; else if (f2 == 0) s = "false"; else if (max_between >= f2) s = "false"; else if (f1 < 0) s = "maybe"; else if (f1 < f2) s = "false"; else // f1 and f2 known, f1 >= f2 and max_between < f2 s = (num_between == y2-y1-1) ? "true" : "maybe"; } } printf("%s\n", s); } delete[] nodes; delete stat; return true; } int main() { int n = 0; while (solve(n++)); return 0; }