Simple c++ solution using stack and binary search


#1

#define mod 1000000007
#define ll long long

long long productDiv(ll a){
long long int res=1;

for(long long i=1; i*i<=a; i++){
    if(a%i==0){
        res= (res*i)%mod;
        if(a/i!=i)
        res= (res*(a/i))%mod;
    }
}

return res;

}

vector Solution::solve(vector &A, vector &B) {
int n= A.size();
stack sleft, sright;
vector left(n, 0), right(n, 0);

for(int i=0; i<n; i++){
    while(sleft.size()>0 && A[sleft.top()]<=A[i]){
        sleft.pop();
    }
    if(sleft.size()==0){
        left[i]=-1;
    }
    else{
        left[i]=sleft.top();
    }
    sleft.push(i);
}

for(int i=n-1; i>=0; i--){
    while(sright.size()>0 && A[sright.top()]<A[i]){
        sright.pop();
    }
    if(sright.size()==0){
        right[i]=-1;
    }
    else{
        right[i]=sright.top();
    }
    sright.push(i);
}

vector<pair<long long, ll>> freq;

for(ll i=0; i<n; i++){
    ll a= left[i], b=right[i];
    if(a!=-1) a= i-left[i];
    else a= i+1;
    if(b!=-1) b= right[i]-i;
    else b= n-i;
    
    freq.push_back({productDiv((long long)A[i]), a*b});
}

sort(freq.begin(), freq.end(), greater<pair<long long, ll>>());

vector<ll> pre(n);
vector<int> ans;

for(int i=0; i<n; i++){
    if(i==0) pre[i]= freq[0].second;
    else
    pre[i]= pre[i-1]+freq[i].second;
}
  
ll q= B.size();

for(int i=0; i<q; i++){
    ll b= B[i];
    ll l=0, r= n-1;
    int answer;
    
    while(l<=r){
        ll mid= (l+r)/2;
        if(pre[mid]>=b){
            answer= freq[mid].first;
            r= mid-1;
        }
        else{
            l= mid+1;
        }
    }
    
    ans.push_back(answer);
}

return ans;

}