#include <iostream> using namespace std; struct Node { Node *leftChild = NULL, *rightChild = NULL; int start, end; bool red = false, yellow = false, blue = false; Node(int start, int end) { this->start = start; this->end = end; } }; void setColor(int color, Node *n) { if (color == 1) { n->yellow = true; } else if (color == 2) { n->blue = true; } else if (color == 3) { n->red = true; } } void buildSubtree(Node *n) { if (n->start != n->end) { n->leftChild = new Node(n->start, (n->start + n->end) / 2); buildSubtree(n->leftChild); n->rightChild = new Node(((n->start + n->end) / 2) + 1, n->end); buildSubtree(n->rightChild); } } void traverseTree(Node *n) { if (n->leftChild != NULL) { traverseTree(n->leftChild); } cout << n->start << "-" << n->end << ": " << (n->red ? "red " : "") << (n->yellow ? "yellow " : "") << (n->blue ? "blue" : "") << endl; if (n->rightChild != NULL) { traverseTree(n->rightChild); } } int traverseTree(int sum, Node *n) { if (n->leftChild == NULL && n->rightChild == NULL) { if (!n->red && n->blue && n->yellow) return 1; else return 0; } else { if (n->leftChild != NULL) { sum += traverseTree(0, n->leftChild); } if (n->rightChild != NULL) { sum += traverseTree(0, n->rightChild); } return sum; } } bool intersect(int l1, int r1, int l2, int r2) { return !((r1 < l2) || (r2 < l1)); } void inputInterval(int start, int end, int color, Node *n) { if (!n->red) { if (n->start >= start && n->end <= end) { setColor(color, n); if (color != 5) { if (n->leftChild != NULL) { if (intersect(start, end, n->leftChild->start, n->leftChild->end)) { inputInterval(start, end, color, n->leftChild); } } if (n->rightChild != NULL) { if (intersect(start, end, n->rightChild->start, n->rightChild->end)) { inputInterval(start, end, color, n->rightChild); } } } } else { if (intersect(start, end, n->leftChild->start, n->leftChild->end)) { inputInterval(start, end, color, n->leftChild); } if (intersect(start, end, n->rightChild->start, n->rightChild->end)) { inputInterval(start, end, color, n->rightChild); } } } } int main() { int n, m; cin >> n >> m; Node * root = new Node(1, n); buildSubtree(root); for (int i = 0; i < m; i++) { int l, r, k; cin >> l >> r >> k; inputInterval(l, r, k, root); } cout << traverseTree(0, root); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <iostream> using namespace std; struct Node { Node *leftChild = NULL, *rightChild = NULL; int start, end; bool red = false, yellow = false, blue = false; Node(int start, int end) { this->start = start; this->end = end; } }; void setColor(int color, Node *n) { if (color == 1) { n->yellow = true; } else if (color == 2) { n->blue = true; } else if (color == 3) { n->red = true; } } void buildSubtree(Node *n) { if (n->start != n->end) { n->leftChild = new Node(n->start, (n->start + n->end) / 2); buildSubtree(n->leftChild); n->rightChild = new Node(((n->start + n->end) / 2) + 1, n->end); buildSubtree(n->rightChild); } } void traverseTree(Node *n) { if (n->leftChild != NULL) { traverseTree(n->leftChild); } cout << n->start << "-" << n->end << ": " << (n->red ? "red " : "") << (n->yellow ? "yellow " : "") << (n->blue ? "blue" : "") << endl; if (n->rightChild != NULL) { traverseTree(n->rightChild); } } int traverseTree(int sum, Node *n) { if (n->leftChild == NULL && n->rightChild == NULL) { if (!n->red && n->blue && n->yellow) return 1; else return 0; } else { if (n->leftChild != NULL) { sum += traverseTree(0, n->leftChild); } if (n->rightChild != NULL) { sum += traverseTree(0, n->rightChild); } return sum; } } bool intersect(int l1, int r1, int l2, int r2) { return !((r1 < l2) || (r2 < l1)); } void inputInterval(int start, int end, int color, Node *n) { if (!n->red) { if (n->start >= start && n->end <= end) { setColor(color, n); if (color != 5) { if (n->leftChild != NULL) { if (intersect(start, end, n->leftChild->start, n->leftChild->end)) { inputInterval(start, end, color, n->leftChild); } } if (n->rightChild != NULL) { if (intersect(start, end, n->rightChild->start, n->rightChild->end)) { inputInterval(start, end, color, n->rightChild); } } } } else { if (intersect(start, end, n->leftChild->start, n->leftChild->end)) { inputInterval(start, end, color, n->leftChild); } if (intersect(start, end, n->rightChild->start, n->rightChild->end)) { inputInterval(start, end, color, n->rightChild); } } } } int main() { int n, m; cin >> n >> m; Node * root = new Node(1, n); buildSubtree(root); for (int i = 0; i < m; i++) { int l, r, k; cin >> l >> r >> k; inputInterval(l, r, k, root); } cout << traverseTree(0, root); } |