Time Limit Exceeded error in c++


#1

I have solved the problem with the following algorithm:

  1. I created a map to store frequency of each element in array G. The algorithm iterates through every element: If previous element is smaller, then iterates from previous element’s largest sub array limits, else iterates starting from current element itself; in both directions till it’s largest sub array is found. At the same time, it also finds each element’s product of divisors and stores using this in the map.

vector Solution::solve(vector &A, vector &B) {
    map freq;
    int L=0, H=0, l, h, prev, j;
    long long a1, a2;
    int p;
    
    for(int i=0; i<A.size(); i++){
        prev= (i==0)?-1:A[i-1];
        a1= A[i];
        if(prev<a1){
            l=L;
            h= (H=0 && A[l]<a1){
                l--;
            }
            while(h<A.size()-1 && A[h+1]<=a1){
                h++;
            }
            L=(l==i)?l:l+1; H=h;
        }
        else{ 
            L=i;
            h=i;
            while(h<H && A[h+1]<=a1){
                h++;
            }
            H=h;
        }
        p=1;
        for(j=2; j<=sqrt(a1); j++){
            if(a1%j==0) p++;
        }
        p*=2;
        if(sqrt(a1)==(int)sqrt(a1)) p--;
        a2=a1;
        for(int k=1; k<(p/2); k++){
            a2=(a2*a1)%(1000000007);
        }
        if(p%2!=0)  a2=(long long)(a2*pow(a1,0.5))%(1000000007);
        freq[a2]+=(i-L+1)*(H-i+1);
    }
  1. Now this map is sorted by transferring its contents to a vector of pairs (using a custom sorting function). Further, I consecutively add the frequencies (cumulative frequency) for each value in sorted vector g.

    vector g;
    vector x;
    
    copy(freq.begin(), freq.end(), back_inserter<vector>(g));
    sort(g.begin(), g.end(), sort_fn);
    
    prev=0;
    for(int i=0; i<g.size(); i++){
        g[i].second+=prev;
        prev= g[i].second;
    }
  1. Finally, for finding B[i], I binary search over the cumulative frequencies and store the result in vector x.

    for(auto i= B.begin(); i!=B.end(); i++){
        x.push_back(g[bin_search(g, *i-1, 0, g.size()-1)].first);
    }
    
    return x;
}

The functions for sorting and binary search are below.


bool sort_fn(const pr& l, const pr& r){
    return r.first<l.first;
}

int bin_search(vector &g, int q, int l, int r){
    //cout<<l<<" "<<g[l].second<<" "<<q<<" "<<r<<" "<<g[r].second<<endl;
    int m= (l+r)/2;
    if(l==m){
        if(qg[l].second)  return l+1;
    }
    
    if(q==g[m].second) return m+1;
    else if(q<g[m].second) return bin_search(g, q, l, m);
    else return bin_search(g, q, m, r);
}

I have optimized my algorithm to the best of my ability. If there’s something I am missing out please let me know. Thanks.