Link to problem: https://www.spoj.com/problems/FREQUENT/

I know this is quite a famous problem and I have searched extensively about it , but my attempts at debugging my code have failed.

I use the approach of Segment Trees to solve this problem after having built a frequency array. Run time : $$$O(n)$$$ pre-processing per test case and $$$O(log (n))$$$ to answer each query.

#include<iostream>
#include<algorithm>
#include<unordered_map>
 
using namespace std;
 
const int N=200000;
 
int a[N],t[4*N],b[N]; //b is the frequency array
 
void build(int v,int tl,int tr){
    if(tl==tr){
        t[v]=b[tl];
    }
    else{
    int tm=(tl+tr)/2;
    build(2*v,tl,tm);
    build(2*v+1,tm+1,tr);
    t[v]=max(t[2*v],t[2*v+1]);
    }
}
 
int query(int v,int tl,int tr,int l,int r){
    if(l>r)
        return -1e9;
    if(l<=tl&&tr<=r)
        return t[v];
    int tm=(tl+tr)/2;
    return max(query(v*2, tl, tm, l, min(r, tm)),
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
int main()
{
      int n,q; 
      while(true){
        scanf("%d", &n);
        if(!n)break;
        scanf("%d", &q);
        unordered_map<int,int>cnt;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            ++cnt[a[i]];
        }
        for(int i=0;i<n;i++){
            b[i]=cnt[a[i]];
        }
        build(1,0,n-1);
         while(q--){
            int l,r;
            scanf("%d %d",&l,&r);
            --l,--r;
            if(a[r]==a[l]){  //This is when all numbers in the range are the same.
                printf("%d\n",r-l+1);
            }
            else{
                /*This is to handle the case as follows :111 22233 4444
                  idx1 and idx2-1 will cover the range 22233 and
                  then we do the max of all three blocks [111] [22233] [4444] which
                  in this case is basically max(3,3,4)=4 */
                int idx1=upper_bound(a+l,a+l+r,a[l])-a;
                int idx2=lower_bound(a+l,a+l+r,a[r])-a;
                int ans=max(max(idx1-l,r+1-idx2),query(1,0,n-1,idx1,idx2-1));
                printf("%d\n",ans);
            }
         }
    }
 return 0;
} 

Link to question :https://www.spoj.com/problems/DIVSUM2/

My approach : -> Find all prime factors of the number below 1 million . Store the frequency of prime factors in a vector while repeatedly dividing the number by the factor , then use the formula to calculate the sum of factors .

->Now if there is a number left ,then that will be either prime or product of two primes. I try to check primality using Miller–Rabin. If number is not prime , then using rho-pollard , I try to generate one of the prime factors , divide to get another and then proceed accordingly.

However, I am getting TLE. I would like to know where I am going wrong . Is it the implementation or the approach ? Thank you.

#include<bits/stdc++.h>

using namespace std;

#define MOD 10000000007

using ll = unsigned long long ;

const ll million=1000000;

vector<ll>v(50000);

ll pow_expo(ll a,ll b)
{

    ll res=1;
    while(b>0)
    {
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
return res;
}


ll pow_exp(ll a,ll b,ll n)
{
    a%=n;
    ll result=1;
    while(b>0)
    {
        if(b&1)
            result=result*a%n;
        a=a*a%n;
        b>>=1;
    }
return result;
}

bool miller_rabin_test(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=pow_exp(a,d,n);
    if(x==1||x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==(n-1))
            return true;
    }
return false;
}

bool is_prime(ll n,ll k)
{
    if(n<=1||n==4)
    return false;
    if(n==2||n==3)
        return true;
    ll d=(n-1);
    while(d%2==0)
    {
        d/=2;
    }
    for(int i=1;i<=k;i++)
    {
        if(!miller_rabin_test(d,n))
            return false;
    }

return true;
}

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    a%=b;
        return gcd(b,a);
}

ll f(ll x)
{
    return ((x*x)+1);
}
ll rho_pollard(ll n)
{
     if(n%2==0)
        return 2;

    ll x=rand(),y=rand(),d=1;

    while(d==1)
    {
        x=(f(x))%n;

        y=(f(f(y)))%n;

        d=gcd(abs(x-y),n);
    }

    return d;
}

ll factorize(ll n)
{
    ll temp=n;
    for(int i=2;i*i<=n;i++)
    {
        if(i>million)
            break;
        while(n%i==0)
        {
            v[i]++;
            n/=i;
        }
    }
    ll sum=1;
        for(ll i=2;i<v.size();i++)
        {
            if(v[i]>0)
                sum*=(pow_expo(i,v[i]+1)-1)/(i-1);
        }

  if(n>1&&is_prime(n,3))
  {
      sum*=(n+1);
       return (sum-temp) ;
  }
  else if(n>1)
  {
            int f1=rho_pollard(n);
            int f2=n/f1;
            sum*=(f1+f2+2);
             return (sum-temp) ;
  }
return (sum-temp) ;

}

int main()
{
    ll q;
    scanf("%I64d",&q);
    while(q--)
    {
        ll n;
        scanf("%I64d",&n);
        fill(v.begin(),v.end(),0);
        printf("%I64d\n",factorize(n));
    }


}

Link to problem :https://mirror.codeforces.com/contest/1034/problem/A

Link to my submission: https://mirror.codeforces.com/contest/1034/submission/46372547

My approach: I divided the vector of the numbers by their gcd. Then I tried to find largest subsequence having gcd greater than 1. To do that , I used the Sieve of Eratosthenes to calculate least prime factor of every number upto 1.5*10^7 and stored it in array Primes. In the factorise function , I just increase the count of divisors and then return the answer(n-count of the divisor that occurred maximum number of times).

My code gives wrong answer for test case #9. The different between jury's answer and mine is small though . Also I have read the editorial and my approach is same as that of the editorial . I think the problem is with the sieve maybe , should it be in linear time? . Thank you .

Link to the question :https://www.spoj.com/problems/FACTCG2/

Link to code : https://ideone.com/4JlHQE

My approach : I basically created a vector Primes where I stored least prime factor of every number . Then for each input , I divide it by its least prime factor and then display the factors . But Judge gives me wrong answer .

Here is the link to the problem :http://mirror.codeforces.com/contest/1073/problem/D

Here is the link to my submission : http://mirror.codeforces.com/contest/1073/submission/44895822

It shows TLE on test case #8.