C++ Solution | Array | Ordered Multiset | Policy Based Data Structure |
Intuition\nUse Policy Based Data Structure (Ordered multiset).\n\n# Complexity\n- Time complexity: O(nlog(n))\n Add your time complexity here, e.g. O(n) \n\n- S
# Intuition\nUse Policy Based Data Structure (Ordered multiset).\n\n# Complexity\n- Time complexity: $$O(nlog(n))$$\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;\ntypedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; \n// find_by_order, order_of_key\n\nclass Solution {\npublic:\n\n    int greaterCount(pbds &st, int val)\n    {\n        return st.size() - st.order_of_key(val+1);\n    }\n    vector<int> resultArray(vector<int>& a) {\n        \n        int n = a.size();\n        vector<int> a1, a2;\n        a1.push_back(a[0]);\n        a2.push_back(a[1]);\n\n        pbds st1, st2;\n        st1.insert(a[0]);\n        st2.insert(a[1]);\n\n        for(int i=2 ; i<n ; i++)\n        {\n            int gC1 = greaterCount(st1, a[i]);\n            int gC2 = greaterCount(st2, a[i]);\n\n            if(gC1 > gC2)\n            {\n                a1.push_back(a[i]);\n                st1.insert(a[i]);\n            }else if(gC1 < gC2)\n            {\n                a2.push_back(a[i]);\n                st2.insert(a[i]);\n            }else\n            {\n                if(a1.size() <= a2.size())\n                {\n                    a1.push_back(a[i]);\n                    st1.insert(a[i]);\n                }else\n                {\n                    a2.push_back(a[i]);\n                    st2.insert(a[i]);\n                }\n            }\n        }\n\n        for(auto &v: a2) a1.push_back(v);\n        return a1;\n    }\n};\n```
['Array', 'C++']