AVL tree + max size propagation
Approach\n\n## Base tree \n\nThe problem can be handled quite well by the binary tree where each node keeps a value and left and right bounds. \n\n\nclass TreeN
# Approach\n\n## Base tree \n\nThe problem can be handled quite well by the binary tree where each node keeps a value and left and right bounds. \n\n```\nclass TreeNode {\n    int _value;   // the node value - the obstacle position\n    int _lbound;  // the nearest left obstacle from the parent\n    int _rbound;  // the nearest right obstacle from the parent\n    TreeNode *_left{};  \n    TreeNode *_right{};\npublic:\n    TreeNode(int value, int lbound, int rbound): _value(value), _lbound(lbound), _rbound(rbound) {\n    }\n    // add an obstacle\n    void add(int value, int lbound = 0, int rbound = numeric_limits<int>::max()) {\n        if (value < _value) {\n            if (_left) _left->add(value, _lbound, _value);  // the node _value is the left bound for the left subtree\n            else _left = new TreeNode{value, _lbound, _value};\n        } else {\n            if (_right) _right->add(value, _value, _rbound); // the node _value is the right bound for the right subtree\n            else _right = new TreeNode{value, _value, _rbound};\n        }\n    }\n    // check if a block fits.     \n    bool check(int pos, int size) const {\n        return (_value - _lbound >= size   // check if the size is enough\n            && (!_left                     // if the subtree is empty we can fit block\n            || _left->check(pos, size)))   // otherwise check in the subtree\n            || (pos - _value >= size && _rbound - _value >= size && (!_right || _right->check(pos, size)));\n    }\n};\n```\n\nYou can pass about 700 test-cases with the above tree. However some heavy case are handled too slow. \n\n## AVL\n\nGood in average, the base binary tree has $O(n)$ complexity for insertion (and lookup) in the worst-case. \nI believe tye test-case 744 is a such worst-case. The common solution is self-balancing thees (Red-black, AVL, Splay, etc). \nHere I chose AVL. \n\n## Size propagation \n\nSome test-cases like 742,743 needs not only a fast tree build but much faster check. \nAt leaves we know that max block size that can be fit is \n`max(value - lbound, rbound - value)`. This size can be propagated to parents to speed the check up. If `maxsize` in subtree less than an incoming block, the block does not fit. And opposite, if an incoming block is not greater than `maxsize` and `rbound` is not greater than `x` the block fits. \n\n## All together\n\n```\nclass AVLTreeNode {\n    int _value;      // the node value - the obstacle position\n    int _lbound;     // the nearest left obstacle from the parent\n    int _rbound;     // the nearest right obstacle from the parent\n    int _height{1};  // the height of the subtree for AVL\n    int _maxsize;    // maxsize for subtree for propagation\n    AVLTreeNode *_left{};\n    AVLTreeNode *_right{};\n    // right node rotation for AVL\n    static AVLTreeNode *_rightRotate(AVLTreeNode *y) {\n        // standard part\n        AVLTreeNode *x = y->_left;\n        AVLTreeNode *t2 = x->_right;\n        x->_right = y;\n        y->_left = t2;\n        y->_updateHeight();\n        x->_updateHeight();\n        // special part: rotate bounds and amend propagation\n        x->_rbound = y->_rbound;\n        x->_lbound = y->_lbound;\n        y->_lbound = x->_value;\n        y->_updateMaxSize();  \n        x->_updateMaxSize();\n        return x;\n    }\n    // left node rotation for AVL\n    static AVLTreeNode *_leftRotate(AVLTreeNode *x) {\n        AVLTreeNode *y = x->_right;\n        AVLTreeNode *t2 = y->_left;\n        y->_left = x;\n        x->_right = t2;\n        x->_updateHeight();\n        y->_updateHeight();\n        y->_rbound = x->_rbound;\n        y->_lbound = x->_lbound;\n        x->_rbound = y->_value;\n        x->_updateMaxSize();\n        y->_updateMaxSize();\n        return y;\n    }\n    void _updateHeight() {\n        _height = 1 + max(height(_left), height(_right));\n    }\n    // node size is maximum of sizes of it subtrees\n    // or bounds if subtrees are empty\n    void _updateMaxSize() {\n        _maxsize = max(_left ? _left->_maxsize : _value - _lbound,\n                      _right ? _right->_maxsize : _rbound - _value);\n    }\npublic:\n    AVLTreeNode(int value, int lbound, int rbound): _value(value), _lbound(lbound), _rbound(rbound) {\n        _maxsize = max(value - lbound, rbound - value);\n    }\n    static int height(const AVLTreeNode *node) {\n        return node ? node->_height : 0;\n    }\n    int getBalance() const {\n        return height(_left) - height(_right);\n    }\n    static AVLTreeNode* add(AVLTreeNode* node, int value, int lbound = 0, int rbound = numeric_limits<int>::max()) {\n        // basic insertion\n        if (!node) return new AVLTreeNode{value, lbound, rbound};\n        if (value < node->_value) {\n            node->_left = add(node->_left, value, node->_lbound, node->_value);\n        } else {\n            node->_right = add(node->_right, value, node->_value, node->_rbound);\n        }\n        // size propagation\n        node->_updateMaxSize();\n        // AVL rotation if node is not balanced\n        node->_updateHeight();        \n        const int balance = node->getBalance();\n        if (balance > 1 && value < node->_left->_value) return _rightRotate(node);\n        if (balance < -1 && value > node->_right->_value) return _leftRotate(node);\n        if (balance > 1 && value > node->_left->_value) {\n            node->_left = _leftRotate(node->_left);\n            return _rightRotate(node);\n        }\n        if (balance < -1 && value < node->_right->_value) {\n            node->_right = _rightRotate(node->_right);\n            return _leftRotate(node);\n        }\n        return node;\n    }\n    bool check(int pos, int size) const {\n        // reject if greater than maxsize\n        if (size > _maxsize) return false;\n        // accept if not greater than maxsize and not limited by `x`\n        if (size <= _maxsize && _rbound <= pos) return true;\n        return (_value - _lbound >= size && (!_left || _left->check(pos, size)))\n            || (pos - _value >= size && _rbound - _value >= size && (!_right || _right->check(pos, size)));\n    }\n};\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        AVLTreeNode* root = AVLTreeNode::add(nullptr, 0);\n        vector<bool> res;\n        for (const auto& query: queries) {\n            // add an obstacle \n            if (query[0] == 1) root = AVLTreeNode::add(root, query[1]);\n            else {                \n                if (query[2] == 1) res.push_back(true);  // always fit, no need to waste time\n                // check in tree\n                else res.push_back(root->check(query[1], query[2]));\n            }\n        }\n        return res;\n    }\n};\n```\n\n# Complexity\nLet $n$ is a number of obstacles and $m$ is a number of blocks. \n\nTime: $O((n + m)\\log n)$. \n$O(n\\log n)$ to build the tree, $m$ lookups in the $\\log n$ depth tree. \n\nMemory: $O(n)$.\nThe tree has $n$ nodes.
['C++']