HackerEarth The Market problem solution

In this HackerEarth The Market problem solution There are N items in a market (indexed from 1 to N) each having a particular cost. The danger value of each item is given by the following pseudo code:

           Danger(cost) {

              danger_val = 0

              for ( each i from 1 to cost) {

                   if( cost modulo i is 0  ) {

                       increase danger_val by 1

                   }

              }

              return danger_val

          }

You are given Q queries that contain a range of items. You need to find the number of pairs of items that have the same danger value.

HackerEarth The Market problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define BASE 31
#define BLOCK 500
typedef unsigned long long int uint64;
typedef long long int int64;
 

int fact[1000006];
int cur[250];
int a[100005];
int64 fin[100005];
int64 ans=0;

struct query{
    int l,r,id;
};

bool cmp(query a,query b){
    if((a.l/BLOCK)!=(b.l/BLOCK))
    return (a.l/BLOCK)<(b.l/BLOCK);
    return a.r<b.r;
}

vector<query>v;

void add(int val){
    ans+=cur[fact[val]];
    cur[fact[val]]++;
}

void del(int val){
    cur[fact[val]]--;
    ans-=cur[fact[val]];
}

int main(){
    fact[1]=1;
    for(int i=2;i<=1000000;i++){
        if(fact[i])
        continue;
        for(int j=i;j<=1000000;j+=i){
            if(!fact[j])
            fact[j]=1;
            
            int mul=1;
            int val=j;
            while((val%i)==0){
                val/=i;
                mul++;
            }
            fact[j]*=mul;
        }
    }
    int n,l,r,q;
    cin>>n;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    
    cin>>q;
    query tmp;

    for(int i=1;i<=q;i++){
        scanf("%d%d",&tmp.l,&tmp.r);
        tmp.id=i;
        v.pb(tmp);
    }
    
    sort(all(v),cmp);
    l=1,r=0;
    
    for(int i=0;i<v.size();i++){
        tmp=v[i];
        while(r<tmp.r){
            r++;
            add(a[r]);
        }
        while(l>tmp.l){
            l--;
            add(a[l]);
        }
        
        while(r>tmp.r){
            del(a[r]);
            r--;
        }
        while(l<tmp.l){
            del(a[l]);
            l++;
        }
        fin[v[i].id]=ans;
    }
    
    for(int i=1;i<=q;i++)
    printf("%lld\n",fin[i]);
    //fclose(stdout);
    return 0;
}

Second solution

#include <bits/stdc++.h>
#define lli long long

using namespace std;

int cnt[1000005];
int A[100005];
int dp[100001][100];
int tot;
int idx[1005];

void pre()
{
    for ( int i = 1; i <= 1000000; i++ ) {
        for ( int j = i; j <= 1000000; j += i ) cnt[j]++;
    }
    return;
}

int main()
{
    pre();
    int n,q,x,y;
    lli ans;

    tot = 1;

    cin >> n;
    assert(n >= 1 && n <= 100000);

    for ( int i = 1; i <= n; i++ ) {
        cin >> A[i];
        assert(A[i] >= 1 && A[i] <= 1000000);
        A[i] = cnt[A[i]];
        if ( !idx[A[i]] ) idx[A[i]] = tot++;
        A[i] = idx[A[i]];
    }

    assert(tot <= 100);

    for ( int i = 1; i <= n; i++ ) {
        for ( int j = 1; j < tot; j++ ) dp[i][j] = dp[i-1][j];
        dp[i][A[i]]++;
    }

    cin >> q;

    while ( q-- ) {
        cin >> x >> y;
        assert(x >= 1 && x <= n);
        assert(y >= 1 && y <= n);
        assert(x <= y);

        ans = 0;
        for ( int i = 1; i < tot; i++ ) {
            lli val = dp[y][i] - dp[x-1][i];
            val = (val*(val-1LL))/2;
            ans += val;
        }

        cout << ans << endl;
    }
    return 0;
}