Modified Binary Search Solution | C++ | Accepted | Expect TLE if input has many equal elements
Intuition\nMaintain a separate pair array and custom sort it.\n\n# Approach\nBuild a modified version of binary search algorithm with some inner loops. You shou
# Intuition\nMaintain a separate pair array and custom sort it.\n\n# Approach\nBuild a modified version of binary search algorithm with some inner loops. You should expect a TLE error here if the input array has a large number of equal elements as if thats the case, we won\'t be making use of the core principle behind sorted array\'s binary search algorithm. \nThanks to Leetcode for making loose test cases and making this accepted!!\n\n# Complexity\n- Time complexity:\n$$O(m)log(n)$$ \nOr $$O(m*n)$$ in worst case if input is heavily skewed. By skewed I mean large number of equal elements.\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nbool mycmp(pair<int, int> a, pair<int,int> b){\n    if(a.first==b.first){\n        return a.second<b.second;\n    }\n    return a.first<b.first;\n    }\nclass Solution {\npublic:\n    int n;\n    int global_idx;\n    int bache_hue;\n    \n    int bs(pair<int,int> *a, int &tar, int &aux_index, int s, int e){\n        if(s>e) return -1;\n        int mid=(s+e)/2;\n        if(a[mid].first==tar){\n            while(a[mid].second>aux_index) mid--;\n            while(a[mid].second<aux_index) mid++; \n            return mid;\n        }\n        if(a[mid].first>tar)\n            return bs(a,tar, aux_index,s, mid-1);\n        return bs(a, tar, aux_index,mid+1, e);\n    }\n    void Mark_K_smallest(pair<int, int> *arr, int *vis, int k, long long &total){\n        while(bache_hue>0 && k>0){\n            if(vis[global_idx]==0){\n                vis[global_idx]=1;\n                total=total-arr[global_idx].first;\n                bache_hue--; k--;\n            }\n            else{\n                global_idx++;\n            }\n        }\n    }\n    vector<long long> unmarkedSumArray(vector<int> ori, vector<vector<int>>&q) {\n        int vis[100001]={0};\n        pair<int,int> copy[100001];\n        n=ori.size();\n        for(int i=0;i<n;++i){\n            copy[i]=make_pair(ori[i],i);\n        }\n        long long total=0L;\n        vector<long long> ans;\n        ans.clear();\n        for(int x:ori)\n            total=total+x;\n        \n        global_idx=0;\n        bache_hue=n;\n        sort(copy, copy+n, mycmp);\n        for(int j=0;j<q.size();++j){\n            int idx=bs(copy, ori[q[j][0]],q[j][0], 0, n-1);\n            if(vis[idx]==0){\n                vis[idx]=1;\n                total=total-copy[idx].first;\n                bache_hue--;\n            }\n            Mark_K_smallest(copy, vis, q[j][1], total);\n            ans.push_back(total);\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Sorting', 'C++']