CSES Colllecting Numbers

help
1

Here is the link to the problem.

I am trying to solve this problem using binary search, but it gives TLE. Can anyone Help?

    #include<bits/stdc++.h>
using namespace std;

int binaryS(vector<pair<int,int> > a, int key){
    int low = 0;
    int high = a.size()-1;

    while(low<high){
        int mid = (low+high)/2;
        if(a[mid].first == key){
            return a[mid].second;
        }else if(a[mid].first > key){
            high = mid-1;
        }else{
            low = mid+1;
        }
    }

    return -1;

}

int main(){

    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int n;
    cin>>n;

    vector<pair<int,int> > a;
    for(int i = 0;i<n;i++){
        int x;
        cin>>x;
        a.push_back({x,i+1});
    }

    sort(a.begin(),a.end());

    int index = 0;
    int ans = 0;
    for(int i = 1;i<=n;i++){
        int temp = binaryS(a,i);
        if(temp<index){
            ans++;
        }
        index = temp;
    }

    cout<<ans<<endl;

}
1 Like
2 
int binaryS ( vector< pair< int, int > > a , int key )

Here, you are passing vector by value. This means everytime you call binaryS (a, i), a new copy of vector< pair< int, int > > a is created and passed to that function. This takes O(N) time; making your total time complexity O(N^2log(N)).
Solution :
Pass by reference:

int binaryS ( vector< pair< int, int > >& a , int key )

OR
Make the vector global.

3

Thanks, @ameybhavsar, I got it.

1 Like