 # 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.