Solve Using Ordered Set
Pre-requisite Knowledge\nHeader files needed for ordered set:\n\n#include<ext/pb_ds/assoc_container.hpp>\n#include<ext/pb_ds/tree_policy.hpp>\nusing namespace _
# Pre-requisite Knowledge\nHeader files needed for ordered set:\n```\n#include<ext/pb_ds/assoc_container.hpp>\n#include<ext/pb_ds/tree_policy.hpp>\nusing namespace __gnu_pbds;\n```\n```\ntypedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;\n```\nHere, ```greater_equal<int>``` will make the ordered set to work as multiset and arrange the elements in non-increasing order.\n\n```order_of_key(k)``` will give count of no. of elements in ordered set greater than k in time complexity of 0(logN).\n# Approach\n1) Requires two ordered set arr1 & arr2 for calculating ```greaterCount()``` and two vectors brr1 & brr2 for tracking the order of elements pushed in arr1 & arr2 since in ordered set the elements will arrange themselves in non-increasing order.\n2) Push the nums[0] to arr1 & brr1, and nums[1] to arr2 & brr2.\n3) Iterate through the remaining elements of given vector and for each element compute the ```greaterCount()``` by using ```order_of_key(k)``` and push the elements in arr1, brr1 & arr2, brr2 according to the given conditions.\n4) Finally, append elements of brr1 & brr2 to ans vector and return it.\n\n# Complexity\n- Time complexity: O(NlogN)\n\n- Space complexity: 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\ntypedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        int n = nums.size();\n        pbds arr1, arr2;\n        vector<int> brr1, brr2;\n        arr1.insert(nums[0]);\n        brr1.push_back(nums[0]);\n        arr2.insert(nums[1]);\n        brr2.push_back(nums[1]);\n        int fir = 1, sec = 1;\n        for(int i = 2; i<n; i++) {\n            if(arr1.order_of_key(nums[i]) > arr2.order_of_key(nums[i])) {\n                arr1.insert(nums[i]);\n                brr1.push_back(nums[i]);\n                fir++;\n            }\n            else if(arr1.order_of_key(nums[i]) < arr2.order_of_key(nums[i])) {\n                arr2.insert(nums[i]);\n                brr2.push_back(nums[i]);\n                sec++;\n            }\n            else {\n                if(fir<=sec) {\n                    arr1.insert(nums[i]);\n                    brr1.push_back(nums[i]);\n                    fir++;\n                }\n                else {\n                    arr2.insert(nums[i]);\n                    brr2.push_back(nums[i]);\n                    sec++;\n                }\n            }\n        }\n        vector<int> ans;\n        ans.reserve(n);\n        for(int i = 0; i<brr1.size(); i++) {\n            // cout<<brr1[i]<<endl;\n            ans.push_back(brr1[i]);\n        }\n        for(int i = 0; i<brr2.size(); i++) {\n            cout<<brr2[i]<<endl;\n            ans.push_back(brr2[i]);\n        }\n        return ans;\n    }\n};\n```
['Ordered Set', 'C++']