Ordered Statistics Set | Policy Based DS | O(NlogN)
Complexity\n- Time complexity: O(nlogn)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g. O(n) \n\n
# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <ext/pb_ds/assoc_container.hpp> \n#include <ext/pb_ds/tree_policy.hpp> \nusing namespace __gnu_pbds; \n\n#define os tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update>\n\n#define pb push_back\n\nclass Solution {\npublic:\n\n    vector<int> resultArray(vector<int>& nums) {\n        os arr1;os arr2;\n        vector<int>a1;vector<int>a2;\n        int ct1, ct2;\n\n        arr1.insert(nums[0]);arr2.insert(nums[1]);\n        a1.pb(nums[0]);a2.pb(nums[1]);\n\n        for(int i=2;i<nums.size();i++){\n            ct1 = arr1.order_of_key(nums[i]);\n            ct2 = arr2.order_of_key(nums[i]);\n\n            if(ct1 > ct2){\n                a1.pb(nums[i]);arr1.insert(nums[i]);\n            }\n            else if(ct1 < ct2){\n                a2.pb(nums[i]);arr2.insert(nums[i]);\n            }\n            else{\n                if(a1.size()<=a2.size()){\n                    a1.pb(nums[i]);arr1.insert(nums[i]);\n                }\n                else {\n                    a2.pb(nums[i]);arr2.insert(nums[i]);\n                }\n            }\n        }\n        for(int j=0;j<a2.size();j++)a1.pb(a2[j]);\n\n        return a1;\n    }\n};\n```
['Ordered Set', 'C++']